worldi 의 성장일기

알고리즘 Union-find 풀이 과정 1 ≤ k ≤ 10^12 이하이므로 long 으로 자료형을 설정한다. 주의사항 : 배열 같은 경우, index를 long으로 설정하지 못한다. → Map 자료구조 관리하여야 한다. 어려웠던 점 : parent를 찾을 때 일반적으로 배열을 사용했는데 map 자료구조를 떠올려야 했다. 시간초과 난 부분 맨 처음에 Map을 parent[i] = i 와 같은 식으로 k범위 까지 초기화 시켜줬는데, 시간초과 난다. parent를 계속 갱신 시켜주며, 가장 가까운 호텔을 parent로 다시 갱신한다. 코드 import java.util.*; class Solution { public Map parent = new HashMap(); public long findParent(l..

알고리즘 DP 풀이 과정 일단 생각나는 대로 짜봤다. 예상대로 시간초과가 난다. n이 최대 100이므로, 시간 복잡도가 2^100 이기 때문이다. 이를 dp로 메모이제이션 하는 작업이 필요할 것 같다. public static void dfs(int start, int end, int sum, int answer) { if (start == end) { if (sum == answer) { total++; } return; } int tempSum = sum + arr[start]; if (0

알고리즘 DP 풀이 과정 n이 최대 2000이므로, 브루트 포스는 안될 것 같다. → 자연스레 DP를 하는 방향으로 갔다. DP는 작은 문제를 → 큰문제로 확장시켜 나가는 방식이다. 즉, 크기를 확장시키는 순서가 있어야 한다. ex) 13152 같은 경우, 양 끝쪽만 빠져나가는 것을 확인 할 수 있었다. 따라서 다음과 같은 점화식을 도출해냈다. BaseCode가 중요한데, start==end 일 경우, 맨 마지막 숫자이므로, dp[start][start] = arr[start] * n이 된다. 이를 코드로 옮기면 다음과 같다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import ..

알고리즘 BFS 풀이 과정 조합 개수로 반복 DFS를 돌리면서 해볼까 생각했는데, 이는 N ≤ 10 정도 일때만 통과한다. 지금은 1≤ N ≤ 50 이므로 시간 초과 또는 메모리 초과가 난다. 다른 풀이 방법을 생각했어야 했는데, 한쪽 문을 start 지점으로 정하고, 다른 문을 만날때까지 BFS를 진행한다. PriorityQueue는 거울의 최소 개수로 정렬되게 한다. ! 를 만나면, 방향을 바꿀 수 있다. 즉 90도 방향을 바꾸고 PriorityQueue에다가 넣어준다. ‘*’ 를 만나면 벽이므로 이동할 수 없다. 그 외 다른 것들은 방향을 직진해서 갈 수 있다. 이를 코드에 옮겼고, 다음과 같이 같다. 트러블 슈팅 원래는 코드를 다음과 같이 짰었다. 이 조건을 통해 90도 체크가 되는 지 확인했었다..

알고리즘 다이나믹 프로그래밍 풀이 방법 dp[i][j] = 현재 합은 i이고, k개의 수가 남았을 때 경우의 수. ex) dp[20][2]일때, dp[20][2] = dp[20][1] + dp[19][1] + dp[18][1] + … 로 표현할 수 있다. 해당 식을 일반화 한다면, dp[i][j] = dp[i-j][k-1] ( 0≤ j ≤ i ) 이다. dp의 base 식은 dp[0][0] = 1이다. 0을 만들기 위해서 남은 수가 없을 때 경우의 수는 1가지이기 때문이다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; ..