백준6 백준 9251번 : LCS[java] 1. 첫 번째 문자열(s1)과 두 번째 문자열(s2)를 입력받는다. 2. dp에 사용할 배열 dp[1001][1001]을 만든다. ㄴ dp[i][j]는 s1의 i번째와 s2의 j번째 문자까지 비교했을 때 최장 공통 부분수열이다. 3. s1의 i번째 문자와 s2의 j번째 문자를 비교하고 같다면 dp[i][j] = dp[i-1][j-1] +1 이고, → s1의 i번째 문자와 s2의 j번째 문자를 이번 dp[i][j]에서 공통 문자로 사용했기 때문에 직전까지의 최댓값에 +1을 한다. 4. s1의 i번째 문자와 s2의 j번째 문자를 비교하고 다르다면 dp[i][j] = max(dp[i-1][j] , dp[i][j-1]) 이다. → i번째 문자와 j번째 문자가 다르기 때문에 직전 문자열에 각각 추가하여 비교한 최.. 2023. 2. 22. 백준 17136번 : 색종이 붙이기[java] 1. (0,0)부터 (9,9)까지 탐색을 진행합니다. 2. 탐색중 "1"을 만나면 사용가능한 가장 큰 색종이를 사용합니다. - 사용 가능한 색종이가 없는 경우 - (9,9)에 도달한 경우 - 현재 사용한 색종이의 수가 최솟값보다 커진 경우 ▶ 이 3가지 경우에는 직전의 "1"로 돌아가 이전에 붙였던 색종이를 때고 한 단계 작은 색종이를 붙이고 탐색을 재개합니다. 3. (9,9)에 도달한 경우에는 사용한 색종이의 최솟값을 갱신합니다. import java.io.InputStreamReader; import java.io.BufferedReader; import java.io.IOException; import java.util.ArrayList; public class Main{ static int[][].. 2023. 2. 21. 백준 11437번 : LCA[java] 1. 각 노드에 인접한 모든 노드를 저장한다(edge) 2. edge를 바탕으로 각 노드들의 높이와 부모노드를 구한다. 3. 입력받은 n1과 n2중 더 깊은 노드를 위로 올리면서 같은 높이로 맞춘다. 4. 두 노드에서 한 칸씩 위로 올라가며 비교하는 것을 공통 조상이 나올 때 까지 반복한다. import java.io.InputStreamReader; import java.io.BufferedReader; import java.io.IOException; import java.util.ArrayList; public class Main{ static ArrayList edge = new ArrayList(); static int[] parents; // parents[i] = i의 부모 static in.. 2023. 2. 15. 백준 16236번 : 아기 상어[java] 1. 상어의 위치에서 bfs를 시작해 최단 거리에 있는 먹을 수 있는 물고기의 위치를 모두 저장해둡니다. → 모든 위치를 저장하는 이유는 하나의 최단거리를 발견하자마자 이동하면 가장 위쪽 우선, 가장 왼쪽 우선이라는 조건을 만족하지 않을 수 있기 때문에 모든 위치를 저장한 후 비교하여 이동할 위치를 결정합니다. 2. 다음으로 이동할 곳이 없거나 먹을 수 있는 물고기가 없을 때 까지 1번을 반복합니다. import java.io.InputStreamReader; import java.io.BufferedReader; import java.io.IOException; import java.util.LinkedList; import java.util.PriorityQueue; import java.util.Q.. 2023. 2. 13. 이전 1 2 다음 반응형
