아이디어 dp[i][j] 를 1번째 수열의 i번째 문자까지, 2번째 수열의 j번째 문자까지 고려했을 때 LCS 값이라고 정의한다면 dp[i][j] 는 다음과 같은 점화식을 가진다. 1번째 수열의 i 번째 문자와 2 번째 수열의 j 번째 문자가 동일한 경우 dp[i][j] = dp[i - 1][j - 1] + 1 동일하지 않은 경우에는 dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) ACAYKP, CAPCAK 가 주어질 경우 dp[3][5] 는 ACA 와 CAPCA 의 LCS 값을 의미하게 되고 [3][5] 에 해당하는 문자가 'A' 로 동일하기 때문에 AC 와 CAPC 의 LCS 값에 1 을 추가한 게 곧 ACA, CAPCA 의 LCS 가 된다. dp[2][5] 는 ..
아이디어 dp[i] 를 최대 i 만큼의 무게를 넣을 수 있는 배낭을 맸을 때 넣을 수 있는 물건들 가치의 최대값이라고 정의를 한다면 물건의 무게가 각각 6 4 3 5 그 가치가 각각 13 8 6 12 일 때 dp[i] 는 dp[i] = max(dp[i - 6] + 13, dp[i - 4] + 8, dp[i - 3] + 6, dp[i - 5] + 12) 라고 볼 수 있다. 다만 이 때 주의해야할 점은 같은 물건을 배낭에 여러 번 담을 수는 없다는 것이다. 예를 들어 dp[3] 을 계산할 때 무게가 3인 물건을 담는 게 가장 가치가 크게 되는 경우이므로 이미 배낭에 담았는데 dp[6] 을 계산할 때 또 담으면 안 된다는 것이다. 이는 각 물건에 대해 dp[i] 를 갱신하는 과정을 i 의 오름차순이 아닌 내림..
String 객체의 생성 방법 String 타입 객체를 생성하는 방법에는 2가지가 있다. 1. new 연산자를 사용하는 방법 2. literal 을 사용하는 방법 각 방법은 생성 과정에서 차이가 있다. new 연산자를 사용하는 방법은 늘 새로운 객체를 생성해서 JVM 의 Heap 영역에 이를 저장하고 참조하게 되는 반면 literal 을 사용하는 방법은 우선 동일한 literal 로 생성된 객체가 JVM Heap 영역 중 String Constant Pool 이라는 영역에 저장되어 있는지 확인한다. 이미 생성된 객체가 있다면 해당 객체를 참조하게 되고 그렇지 않다면 새로운 객체를 만들어 String Constant Pool 에 저장하고 참조하게 된다. public class Main { public st..
아이디어 1. bfs 탐색을 통해 국경이 열리는 국가들을 하나의 연합으로 묶고 2. (연합 총 인구수 / 연합 국가 수) 를 계산하여 연합으로 묶인 국가들의 인구를 갱신해준다. 3. 이 때 기존 인구 수와 갱신해야 하는 인구 수가 같다면 갱신이 불필요 즉 인구 이동이 일어나지 않으므로 인구 갱신 시 '기존 인구 수와 갱신 인구 수가 같지 않을 때만 인구 이동이 일어났다고 판단한다' 매일 새로운 visited 배열과 함께 1 ~ 3 과정을 수행하고 3 과정에서 '인구 이동이 없었다' 라고 판단이 되면 다음 날로 넘어가지 않고 현재까지 며칠이 소요되었는지를 출력하면 된다. import java.io.BufferedReader; import java.io.IOException; import java.io.In..
아이디어 이 문제는 별다른 아이디어는 필요 없고 문제에서 요구하는 바를 순서에 따라 정확히 구현하기만 하면 되는 문제이다. 노트북에 스티커를 붙이는 과정은 1. 스티커를 붙일 수 있는 가장 왼쪽 상단 위치를 찾는다. 2. 스티커를 붙인다. 3. 만약 붙일 수 있는 위치가 없다면 90도 회전해서 1부터 반복한다. 4. 스티커 회전을 90, 180, 270 도 모두 해봐도 붙일 수 없다면 해당 스티커는 버린다. 따라서 1) 왼쪽 상단 부터 탐색하여 스티커를 붙일 수 있는 가장 왼쪽 상단의 위치를 찾는 메서드 2) 스티커를 붙이는 메서드 3) 스티커를 90도 회전시키는 메서드 이 3가지만 잘 구현해낸다면 해결할 수 있는 문제이다. 풀이코드 import java.io.BufferedReader; import j..
아이디어 (x1, y1) ~ (x2, y2) 까지의 직사각형에 존재하는 값들의 합을 구하기 위해 먼저 (1, 1) 에서 (x, y) 까지의 합을 담고 있는 dp 배열을 만든다. dp[i][j] 를 (1, 1) 에서 (i, j) 까지 만들어지는 직사각형에 존재하는 값들의 합이라고 정의한다면 (x1, y1) ~ (x2, y2) 직사각형에 존재하는 값들의 합은 dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1] 이 된다. (1, 1) 에서 (i, j) 까지 직사각형에 존재하는 값들의 합인 dp[i][j] 에 대한 점화식은 다음과 같이 세울 수 있다. dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j ..
아이디어 이전의 동전 1 문제와 유사한 문제다(https://w-hand.tistory.com/57) dp[i] 를 i 원을 만들기 위해 필요한 최소 동전의 개수라고 정의하고 동전이 1원, 5원, 12원이 있다면 dp[i] = min(dp[i - 1], dp[i - 5], dp[i - 12]) + 1 이 된다. 문제 특성 상 동전의 종류는 입력에 따라 달라지므로 반복문을 사용해서 위의 점화식을 구현해야한다. 그리고 이 때 초기값은 동전 가치의 최대값인 100,000 보다 1 큰 100,001 로 설정한다. (1원짜리 동전으로 100,000 원을 만드는 것이 동전 갯수의 최대 경우이기 때문에 이보다 더 큰 값으로 설정하여 해당 금액을 만들 수 없는 경우를 표현한다) 풀이코드 import java.io.Bu..
아이디어 dp[i] : i 원을 만드는 경우의 수 동전이 1원, 2원, 5원이 있다고 가정하였을 때 단순히 생각해보면 dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 5] 다만 이와 같은 계산 방식은 '사용한 동전의 구성이 같은데, 순서만 다른 것'을 다르게 바라보는 방식이므로 약간의 변형이 필요하다. 위와 같은 방식으로 계산하면 3원을 만드는 방법에는 1) 1 + 1 + 1 2) 1 + 2 3) 2 + 1 3가지가 존재하게 되는데 문제에서 요구하는 바에 따르면 2) 와 3)은 같은 경우로 바라봐야 하므로 1) 1 + 1 + 1 2) 1 + 2 만이 계산될 수 있도록 해야한다. 이는 1원짜리 동전으로 i 원을 먼저 만들고 그 후 2원짜리 동전을 추가하여 i 원을 만들 수 있는 경우의..