처음
이번에는 다이나믹 프로그래밍에 대해서 공부했다. dp라고 줄여서 부르곤 하는 것 같은데, 이것의 정의는 "구하려는 문제의 해를 더 작은 문제의 해로부터 도출해가는 알고리즘" 이다. 사실 이건 내가 공부하고 문제 좀 풀어보고나서 맘대로 표현해본 것이다. 다르게는 "여러 개의 하위 문제를 먼저 푼 후에 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘" 이라고 표현할 수도 있다.
늘 그랬듯이 이게 무슨 말인지 직관적으로 이해하긴 힘들다. 다만 나는 학과 전공에서 dp를 살짝 맛 본 경험이 있었다. 가격을 최소화하기 위한 주문 주기와 주문량을 구하는 문제였는데, 재고비용, 주문비용 등을 변수로 다이나믹 프로그래밍을 적용해 해결한 적이 있었다. 딱 한 번이었지만 dp의 맛을 느끼기엔 충분했다. dp의 핵심은 바로, "점화식으로 표현할 수 있는 무언가를, 아랫 단계부터 차곡차곡 쌓아나가는 느낌" 이라고 생각했다. 적고 보니까 이것도 너무 추상적으로 느껴지긴 한다. 문제를 풀어보면서 맛을 다시 상기시켜봐야겠다.
중간
1. 백준 1463 - 1로 만들기
앞으로 dp 문제를 풀 때는, 다음의 세 단계를 통해 해결할 것이다.
- 테이블 정의하기
- 점화식 찾기
- 초기값 정하기
1번의 테이블이란, 위에서 말했던 차곡차곡 쌓을 작은 해들을 저장할 배열을 말한다. 문제에 따라서 2차원이 된다던가, 다양한 형태를 가질 수 있다.
2번의 점화식은 작고 큰 문제들의 관계를 맺어주는 식이 될 것이다. 초기값은 재귀에서의 base condition처럼 가장 낮은 단계에서의 값을 말한다.
package dynamic;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Map;
public class BOJ1463 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] d = new int[1000001];
d[1] = 0;
for (int i = 2; i <= n; i++) {
d[i] = d[i-1] + 1;
if (i%2 == 0) d[i] = Math.min(d[i / 2] + 1, d[i]);
if (i%3 == 0) d[i] = Math.min(d[i / 3] + 1, d[i]);
}
System.out.println(d[n]);
}
}
- 테이블 정의하기 : d[i] = i를 1로 만들기 위해 필요한 최소 연산 수
- 점화식 찾기 : d[i] = d[i/3] +1 (3으로 나누어떨어질 때), d[i/2] + 1 (2로 나누어떨어질 때), d[i-1] + 1 세 개 중의 최솟값
- 초기값 정의하기 d[1] = 0
이 과정에 적용시켜보니, dp에 문제를 어떻게 써먹어야할 지 감이 딱 온 것 같다. 쪼갠 문제들 사이의 관계를 파악하고,(점화식) 테이블에 단계들을 저장한다.
2. 백준 9095 - 1, 2, 3 더하기
- D[i] = 정수 i를 1, 2, 3의 합으로 나타내는 방법의 수
- D[i] = D[i-1] + D[i-2] + D[i-3]
- 초기값 - D[1] = 1, D[2] = 2, D[3] = 3
예를 들어, 정수 4를 1, 2, 3의 합으로 나타내는 방법의 수는, 정수 5의 그것에도 써먹을 수 있다. 즉, 5를 구하는 문제를 4를 구하는 문제, 3을 구하는 문제 등으로 쪼갠 뒤에 더하는 방식으로 구할 수 있다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class BOJ9095 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int testN = Integer.parseInt(br.readLine());
int[] d = new int[12];
for (int i = 0; i < testN; i++) {
Arrays.fill(d, 0);
d[0] = 0; d[1] = 1; d[2] = 2; d[3] = 4; //(1 2) (2 1) (1 1 1)
int n = Integer.parseInt(br.readLine());
for (int j = 4; j <= n; j++) {
d[j] += d[j-1] + d[j-2] + d[j-3];
}
System.out.println(d[n]);
}
}
}
3. 백준 2579 - 계단 오르기
앞의 직관적인 문제들과 달리 dp를 약간 응용하는 문제였다. 아래쪽의 계단들에서의 최댓값을 잘 모아놓고, 그것을 쌓아나가 정답에 도달하면 되기 때문에 dp의 전형적인 문제였지만, 연속으로 세 개의 계단을 밟으면 안되기 때문에, 밟은 계단을 나타내기 위해 한 차원이 더 필요했다.
- D[i][j] = i번째 계단을 j번 연속으로 연속된 계단을 밟아 도착할 때의 최대 점수
2, 3. 코드 참고
package dynamic;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class BOJ2579 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] score = new int[n+1];
for (int i = 1; i <= n; i++) {
score[i] = Integer.parseInt(br.readLine());
}
int[][] d = new int[301][3];
d[0][0] = 0;
d[0][1] = 0;
d[0][2] = 0;
d[1][0] = 0;
d[1][1] = score[1];
d[1][2] = 0;
if (n == 1) {
System.out.println(score[1]);
return;
} else if (n == 2) {
System.out.println(score[1] + score[2]);
return;
}
d[2][0] = 0;
d[2][1] = score[2]; //불가
d[2][2] = score[1]+score[2];
d[3][0] = 0;
d[3][1] = score[1] + score[3];
d[3][2] = score[2] + score[3];
for (int i = 4; i < score.length; i++) {
for (int j = 0; j < 3; j++) {
//더블짬뿌 해서 도달하는 경우
d[i][1] = Math.max(d[i - 2][j] + score[i], d[i][1]);
// 한단계뛰어서 도달하는 경우
if (j != 0) d[i][j] = Math.max(d[i-1][j-1] + score[i], d[i][j]);
}
}
System.out.println(Math.max(d[n][1], d[n][2]));
}
}
연속으로 밟는 계단이 0인 경우는 없기 때문에 d의 크기는 n*2로 했으면 됐지만, 처음에 문제를 한 단계 이동이 최대 세 번까지로 잘못 이해해서 n*3으로 만들었다. 메모리는 충분했기 때문에 수정은 하지 않았다.
4. 백준 1149 - RGB 거리
이전 문제처럼, 집의 색이 같으면 안된다는 조건이 붙었다. 이차원 배열로 색을 지정했다.
테이블 정의 : D[i][j] = i번째 집을 j색으로 칠할 때 여기까지의 최소 비용
package dynamic;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class BOJ1149 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[][] cost = new int[n + 1][3];
int[][] d = new int[n + 1][3];
for (int i = 1; i < n+1; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < 3; j++) {
cost[i][j] = Integer.parseInt(st.nextToken());
}
}
for (int i = 0; i < 3; i++) {
d[1][i] = cost[1][i];
}
for (int i = 2; i < n+1; i++) {
for (int j = 0; j < 3; j++) {
d[i][j] = Math.min(d[i-1][(j + 1) % 3] + cost[i][j], d[i-1][(j + 2) % 3] + cost[i][j]);
}
}
System.out.println(Math.min(Math.min(d[n][0], d[n][1]), d[n][2]));
}
}
이렇게 되면 각 단계를 j색으로 칠했을 때 최소 비용을 저장하게 된다.
5. 백준 11726 - 2xn 타일링
- D[i] = i번째 줄까지 채우는 경우의 수
- D[i] = D[i-1] + D[i-2]
쉬운 문제였다. i번째 줄 즉, 2*i 사각형을 채우는 경우의 수는, i-1번째 줄까지의 경우의 수에 세로로 세운 타일을 넣는 경우의 수와, i-2번째 줄까지의 경우의 수에 눕힌 타일 두개를 넣는 경우의 수 밖에는 없다.
package dynamic;
import java.io.BufferedReader;
import java.util.Arrays;
import java.util.Scanner;
public class BOJ11726 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
if (n == 1) {
System.out.println(1);
return;
}
long[] d = new long[n + 1];
d[1] = 1;
d[2] = 2;
for (int i = 3; i < n+1; i++) {
d[i] = (d[i - 1] + d[i - 2])%10007;
}
System.out.println(d[n]%10007);
}
}
6. 백준 11659 - 구간 합 구하기 4
10만 개의 원소에서 최대 10만 번 구간을 순회해야 하기 때문에 매번 구간 합을 구하는 방식은 비효율적이다. dp의 부분 문제들의 해를 미리 구해놓는 점을 활용하면 효율적인 시간으로 해결할 수 있다.
D[i] = arr[1]부터 arr[i]까지의 합
D[i] = D[i-1] + arr[i]
package dynamic;
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
/*
* prefix sum이라는 기술!! 기억!!!!
* */
public class BOJ11659 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int[] arr = new int[n+1];
int[] d = new int[n + 1];
st = new StringTokenizer(br.readLine());
for (int i = 1; i < n+1; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
d[1] = arr[1];
for (int i = 2; i < n+1; i++) {
d[i] = d[i - 1] + arr[i];
}
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
bw.write((-1)*d[Integer.parseInt(st.nextToken())-1] + d[Integer.parseInt(st.nextToken())] + "");
bw.newLine();
}
bw.close();
}
}
미리 합을 저장해놓고 꺼내쓰는 prefix sum이라고 불리는 스킬이라고 한다. 기억해두자!!
7. 백준 12852 - 1로 만들기 2
첫번째 문제에서 최소의 연산일 때, n이 1이 되는 과정을 저장해야하는 조건이 추가됐다. dp에서 최소 경로에 관한 정보를 따로 저장하는 방법을 공부할 수 있는 문제였다.
문제는 for문의 모든 단계에서 d[i]를 구할 수 있기 때문에, 이 모든 단계에서 이동한 방법을 저장하면 된다. 우리가 이 정보들을 저장할 배열은 trace[i] = 연산 수를 최소로 만드는, i 이전 단계 숫자라고 정의할 수 있겠다.
그러면 연결리스트가 노드를 따라가듯이 trace 배열의 n번째 인덱스부터, 인덱스가 가리키는 곳을 다시 인덱스로 찾아나가면 될 것이다.
package dynamic;
import java.io.*;
import java.util.Arrays;
//다시보기. 추가적인 정보를 저장해야하는 경우ㅠ
public class BOJ12852 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
int[] d = new int[n + 1]; // i에서 1까지 가는 데 최소 계산
int[] trace = new int[n + 1]; // i번째 위치로 이동하는
d[1] = 0;
for (int i = 2; i < n + 1; i++) {
trace[i] = i-1;
d[i] =d[i - 1] + 1;
if (i % 2 == 0) {
if (d[i] > d[i / 2] + 1) {
d[i] = d[i / 2] + 1;
trace[i] = i / 2;
}
}
if (i % 3 == 0) {
if (d[i] > d[i / 3] + 1) {
d[i] = d[i / 3] + 1;
trace[i] = i / 3;
}
}
}
int cur = n;
while (true) {
System.out.print(cur + " ");
if (cur == 1) break;
cur = trace[cur];
}
}
}
매 단계에서 최단의 방법이 나오면 trace[i]를 갈아치운다.
그러면 trace[n]에는 정수 n으로 다다르기 위한 최선의 이전 단계가 저장되고, 이것을 cur에 저장해서 다시 불러오는 식이다. 너무 참신한 방법이다. 기억하자!!!
끝
dp에 대한 감은 잡았지만, 활용하기는 아직 많이 어려울 것 같다. 우선 dp를 활용해야하는 문제라는 것을 모르고 문제를 접하면 생각해낼 수 있었을 지 모르겠다. 문제를 계속해서 풀어가며 감을 잡아야겠지.
우선 dp의 핵심은 백트래킹이나 bfs 같은 방식에 비해서 탐색의 횟수를 줄일 여지가 있다는 점. (한 번 한 계산은 저장해버리기 때문)과 여러 단계를 쌓아올리는 느낌.
연습문제 출처 : encrypted-def github
DP 개념 출처 : 바킹독 기술 블로그
