백준 11723
2024. 3. 20. 13:06
Algorithm
문제 처음코드 : Hash의 contains 함수가 가장 효율이 좋기에 HashMap의 contains 함수를 이용했고, all 에 대한 HashMap 을 따로 만들어 all 연산 시마다 now에 all 의 값을 할당해 주었다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.HashMap; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { HashMap now = new HashMap(); Buffered..
[백준 1654] 이진탐색
2024. 3. 5. 20:20
Algorithm
처음 짯던 코드는 다음과 같다 만들수 있는 최대 랜선의 길이를 max라 하면 모든 랜선의 길이를 더한 다음 k로 나눈 것이 max의 최댓값이라 생각했고 거기서 n보다 크거나 같을 때까지 1씩 빼가며 max의 값을 구해주는 것이다. public class Baek_1654 { public static void main(String[] args) throws IOException { //K개의 랜선을 모두 N개 이상의 같은 길이의 랜선으로 만들기 //만들 수 있는 최대 랜선의 길이를 구해라 //가지고 있는 랜선 갯수 1
[백준1764]HashSet과 ArrayList의 contains() 시간복잡도
2023. 7. 1. 00:52
Algorithm
간단해 보이지만 이 문제는 ArrayList의 contains() 메서드로 풀면 시간 초과가 난다. HashSet이나 Map을 이용해서 풀면 풀린다. 왜일까? 자료구조 시간복잡도 메서드 구현 방식 HashSet의 contains() O(1) Hashmap을 기반으로 구현 ArrayList의 contains() O(n) indexOf()를 사용해서 contain여부를 결정 HashSet은 HashMap 기반으로 구현되어 있어서 contains 메서드를 실행할때 HashMap.contains() 메서드를 불러온다. 그러므로 시간복잡도는 O(1) 이다. AllayList의 indexOf는 배열에 있는 항목의 수에 따라 시간복잡도가 결정되므로 O(n)이다. ⭐따라서 ArrayList를 사용해서 시간초과가 나거나..
백준7576 토마토
2023. 6. 11. 23:11
Algorithm
처음엔 dfs를 이용해 풀어보려고 했으나 실패했다. bfs를 이용해 익은 토마토가 들어있는(1) 좌표를 q에 넣어주고, 상하좌우에 있는 토마토 중 안익은(0) 토마토가 들어있는 좌표가 있으면 익은 토마토 일수에서 1을 더해준다 즉 depth가 1 깊어질 때마다 1을 추가해 주는 것이다. 이렇게 하면 일수를 계산 가능하다. 그 후 countDay메서드를 통해 가장 깊은 depth를 cnt에 담아주고 depth는 1에서 시작했는데 일수는 0에서부터 시작했으니 날짜를 계산할 때는 1을 빼준다. 최종적으로 checkTomato메서드를 통해 안익은 토마토가 있으면 -1을 출력하고 그렇지 않으면 모든 토마토가 있은것이므로 cnt를 출력한다. import java.io.BufferedReader; import jav..
백준 1041 주사위
2023. 5. 4. 18:05
Algorithm
N에 수에 따른 규칙을 찾아보면 N=1일때는 1,2,3,4,5 면이 보이는 주사위 한개가 놓여지고 N>1일때는 3개 면이 보이는 주사위의 수 : 항상 4개 2개 면 보이는 주사위의 수 (n-1)*4+(n-2)*4 = 4(2n-3) = 8n-12개 1개 면 보이는 주사위의 수 4(n-2)(n-1)+(n-2)^2 = 5n^2 - 16n + 12 가 된다. 따라서 1개 면이 보일때는 정육면체 면중 가장 작은 값이 있는 면이 보여져야 하고 2개 면이 보이는 경우에는 '마주보고 있지 않은' 면 중 합이 가장 작은 두 면이 보여져야 하고 3개 면이 보이는 경우에는 한 모서리를 공유하는 주사위의 세 면의 합이 최소가 되어야 한다. 따라서 마주보는 면 3쌍의 최솟값을 각각 구한 후 더해주면 된다. 여기서 먼저 주의할 ..
백준 1663 -XYZ 문자열
2023. 5. 3. 18:32
Algorithm
CT대비 문제를 풀다가 관련 문제를 풀어봤다. 일단 규칙을 보니 dp[n] = dp[n-3] + dp[n-2] 가 되었고, dp풀면 되겠다고 생각했다. 이 점화식을 이용해 String객체 배열 안에 해당 순서의 String을 저장해 주는 방식으로 풀었다 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; //XYZ 문자열 public class Baek_1663 { static String[] dp; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new Input..
[Java] 이항계수 /백준 1010, 11051
2023. 5. 1. 02:26
Algorithm
문제 풀 때마다 까먹어서 이항계수를 정리해보려 한다. 이항계수 nCr 은 n개중 r개를 선택하는 경우의 수를 의미하며 n!/r!(n-r!)로 나타낼 수 있다 알고리즘에서 이항계수를 구할 때 팩토리얼로 일일히 이항계수를 구하면 int범위를 벗어나 오버플로우가 발생하는 경우가 많다. 따라서 BigInteger를 이용해줄 수 있지만 보통은 재귀를 이용한다. 재귀를 이용할 때에도 시간초과가 날 수 있기 때문에 dp로 풀어주는 것이 일반적이다. 이항계수에는 중요한 규칙 두 가지가 있다. 1.nCr = n-1Cr + n-1Cr-1 2.nC0 = nCn = 1 이를 증명해보자 {a1,a2,a3....an}의 부분집합 중 원소의 개수가 r인 것의 개수는 nCr이다 여기서 원소의 개수가 r인 경우는 두가지로 나뉠 수 있..
[JAVA] DFS,재귀 이해하기/ 백준 2644 촌수계산
2023. 5. 1. 00:38
Algorithm
나는 DFS로 풀었다 처음에 작성한 코드 public class Baek_2644 { static int[][] family; static boolean[] check; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int A = Integer.parseInt(br.readLine()); StringTokenizer st = new StringTokenizer(br.readLine()," "); int S = Integer.parseInt(st.nextToken()); int E = Integer.parseInt(..
[모듈러 연산] 백준 11726 /프로그래머스 - 피보나치 수
2023. 4. 21. 16:57
Algorithm
문제 자체는 점화식만 구한다면 어렵지 않다. dp[1] = 1 / dp[2] = 2 / dp[3] = dp[2] + 2*dp[1] - dp[1] dp[n] = d[n-1] + dp[n-2] 를 이용하여 재귀로 풀어주었다. 그러나 이렇게만 푸니 틀렸다. 찾아보니 계산하려는 수가 너무 커져 오버플로우가 발생했기 때문이었다. 정수형 데이터의 타입을 사용할 때에는 반드시 자신이 사용하고자 하는 데이터의 최소/최대 크기를 고려해야 한다. 오버플로우 : 해당 타입이 표현할 수 있는 '최대 표현 범위'보다 큰 수를 저장할 때 발생하는 현상 언더플로우 : 해당 타입이 표현할 수 있는 '최소 표현 범위'보다 작은 수를 저장할 때 발생하는 현상 위 문제에서는 '방법의 수를 10,007로 나눈 나머지를 출력' 이라는 문구가..