다이나믹 프로그래밍 기본
코테에서 DP를 적용하는 과정
1: 문제가 원하는 정답을 찾기 위해 가장 먼저 완전 탐색 접근을 시도합니다.
2: 완전 탐색 과정에서 탐색하게 되는 경우가 지나치게 많아서 안될 것 같은 경우 DP를 시도합니다.
DP를 푸는 방법
풀고 싶은 가짜 문제 정의
코딩 테스트에서는 다음 3가지 유형의 빈출 주제가 정해져 있습니다.
1: 1~i 번 원소에 대해서 조건을 만족하는 경우의 수
D[i] = 경우의 수
2: i~j 번 원소에 대해서 조건을 만족하는 최댓값 / 최솟값
D[i][j] = i~j 원소에 대해서 조건을 만족하는 최대/최소
3: 수열 A[i...1]과 수열 B[j...1]에 대해 무언가를 계산한 값
D[i][j] = 수열 A[i...1]과 수열 B[j...1]에 대해 무언가를 계산한 값
가짜 문제로 진짜 문제를 풀 수 있는지 검증하기
만들어진 가짜 문제들에 대한 답으로 진짜 문제를 어떻게 구할지 정해야합니다. 예시를 들어서 설명하겠습니다.
진짜 문제 : 수열 A[1...N]에서 조건을 만족하는 부분 수열의 개수
가짜 문제 : 수열 A[1...i]에서 조건을 만족하는 부분 수열의 개수
가짜 문제를 푼다면 D[1], D[2], ... D[N]을 모두 계산한다.
-> D[N]에 적혀 있는 값이 진짜 문제가 원하는 답이다.
초기값을 정하기
가장 작은 원소는 굳이 쪼개지 않아도 문제를 풀 수 있습니다. 때문에 가장 작은 원소의 답안(=초기값)을 미리 초기화해야합니다.
점화식을 구하기
가짜 문제끼리의 연결 고리를 잘 판단해야합니다.
예제
1,2,3 더하기 : 단순 1차원 DP
가짜 문제 정의하기
진짜 문제 = 주어진 n에 대해서 n을 1,2,3의 합으로 표현하는 경우의 수
가짜 문제 = d[i] = i를 1,2,3의 합으로 표현하는 경우의 수
가짜 문제로 진짜 문제를 구할 수 있는가?
d 배열을 전부 채우고 d[n]을 구한다.
초기값은 어떻게 되는가?
d[1] = 1
d[2] = 2
d[3] = 4
점화식을 구해내기
점화식을 구하는 과정은 다음과 같습니다.
1: d[i] 계산에 필요한 탐색 경우를 공통점끼리 묶어냅니다.
2: 묶어낸 부분의 정답을 d 배열을 이용해서 빠르게 계산해봅니다.
예시를 이용해 위 프로세스를 연습해보겠습니다.
공통점을 묶어낼 때는 마지막의 공통을 찾아보는 것만으로 쉽게 찾아낼 수 있습니다. 가장 마지막에 더하는 숫자를 기준으로 파티션을 묶어보겠습니다.
전체 경우의 수는 각 파티션의 경우의 수의 합이 됩니다. 각 파티션이 무엇을 의미하는지 정의해보겠습니다.
각 파티션은 마지막에 1을 더하는 경우 + 마지막에 2를 더하는 경우 + 마지막에 3을 더하는 경우로 나눌 수 있습니다. 즉 점화식은 다음과 같이 도출할 수 있습니다.
D[i-1] + D[i-2] + D[i-3]
계단 오르기 : 2차원 DP
문제의 조건
1: 한 계단 혹은 두개의 계단을 올라갈 수 있음.
2: 연속된 세 개의 계단을 밟을 수는 없음.
3: 도착 계단은 반드시 밟아야한다.
-> 각 계단에서 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총점의 최댓값 구하기
일단 당장 떠오르는 가짜문제로 풀어봅시다.
다음과 같은 가짜 문제를 정의할 수 있습니다.
D[i] = i번째 계단을 밟을 때 최댓값
위와 같은 가짜문제로 점화식을 정의하면 다음과 같습니다.
//한칸 전 계단을 밟을 때 최댓값 + 두칸 전 계단을 밟을 때 최댓값
D[i] = max( D[i-1]+A[i] , D[i-2] + A[i] );
하지만 위 점화식에서는 계단을 어떤식으로 도착했는지의 정보가 없습니다. i-1번째 계단 직전에 i-2번째 계단도 밟았는지에 대한 정보가 누락되어있습니다. 즉 연속된 세 개의 계단을 밟았는지 밟지 않았는지 판단할 수 없습니다.
누락된 정보를 가짜문제에 다시 적용합시다.
D[i][0] = i-1번째 계단을 밟지 않고 I계단을 밟았을 때의 총점 총합.
D[i][1] = i-1번째 계단을 밟고 i계단을 밟았을 때의 총점 총합.
가짜 문제로 결과를 도출하는 방법
max( D[n][0], D[n][1])
점화식
D[i][0] =Max(d[i-2][1], d[i-2][0]) + a[i]
D[i][1] = d[i-1][0] + a[i]
i-1번째를 밟지 않는 경우의 수를 고려하려면 i-2번지를 밟고 올라는 경우의 수만 고려하면 됩니다. 이 때 i-2번지에서는 i-3을 밟던 밟지 않던 i를 연속으로 밟을 때 포함되지 않습니다. 즉 모든 경우의 수를 고려하여 최댓값만 추출합니다.
반대로 i-1번째를 밟아야하는 경우는 i-2번째 칸은 밟으면 안됩니다. d[i-1][0] 만 고려하면 됩니다.
전체 코드
public static void main(String[] args )throws IOException{
int n= Integer.parseInt(buffer.readLine());
int[] scores = new int[301];
for(int i=1; i<=n; i++){
scores[i] = Integer.parseInt(buffer.readLine());
}
int[][] d = new int[301][2];
d[1][0] = 0;
d[1][1] = scores[1];
d[2][1] = scores[1]+scores[2];
d[2][0] = scores[2];
//d[i][0] = i-1번째 계단을 밟지 않았을 때의 총합 중 최대
//d[i][1] = i-1번째 계단을 밟았을 때의 총합 중 최대
//d[i][0] = d[i-2][1], d[i-2][0]
//d[i][1] = d[i-1][0]
for(int i=3; i<=n; i++){
d[i][0] = Math.max(d[i-2][1], d[i-2][0]) + scores[i];
d[i][1] = d[i-1][0]+scores[i];
}
System.out.println(Math.max(d[n][0], d[n][1]));
}
심화) 계단 오르기 문제에서 어떻게 이동할지를 찾으려면?
dp 테이블을 채워 나갈 때에 기록을 함께 한다면 실제 방법 도 찾을 수 있습니다. 이를 역추적 혹은 bactrack이라고 합니다.
어떤 파티션에서 왔는가? 를 기록해야합니다.
prev배열을 추가하여 이동 경로를 추적합니다.prev배열을 사용하여 각 상태로 이전에 어떤 계단에서 왔는지 기록합니다.- 마지막 계단에서 최대 값(
d[n][0]또는d[n][1])을 선택하고, 그 상태에서부터 거꾸로 추적하여 경로를 구합니다. LinkedList를 사용하여 경로를 저장하고, 마지막에 출력합니다.
int n= Integer.parseInt(buffer.readLine());
int[] scores = new int[301];
for(int i=1; i<=n; i++){
scores[i] = Integer.parseInt(buffer.readLine());
}
int[][] d = new int[301][2];
d[1][0] = 0;
d[1][1] = scores[1];
d[2][1] = scores[1]+scores[2];
d[2][0] = scores[2];
int[][] prev = new int[301][2];
prev[2][0] = 0;
prev[2][1] = 1;
for(int i=3; i<=n; i++){
if (d[i-2][1] > d[i-2][0]) {
d[i][0] = d[i-2][1] + scores[i];
prev[i][0] = 1; // 2칸 이전의 1 상태에서 온 것
} else {
d[i][0] = d[i-2][0] + scores[i];
prev[i][0] = 0; // 2칸 이전의 0 상태에서 온 것
}
d[i][1] = d[i-1][0] + scores[i];
prev[i][1] = 0; // 1칸 이전의 0 상태에서 온 것
}
int maxIndex = (d[n][0] > d[n][1]) ? 0 : 1;
System.out.println(Math.max(d[n][0], d[n][1]));
LinkedList<Integer> path = new LinkedList<>();
int current = n;
int state = maxIndex;
while (current > 0) {
path.addFirst(current);
if (state == 1) {
state = prev[current][state];
current -= 1;
} else {
state = prev[current][state];
current -= 2;
}
}
for (int step : path) {
System.out.print(step + " ");
}
System.out.println(Math.max(d[n][0], d[n][1]));
파일 합치기
1: 크기가 존재하는 파일들이 k개 존재함
2: 연속한 두 파일을 하나로 합치려면 합친 크기 만큼의 비용이 발생
3: 전체 k개의 파일을 하나로 합치는 방법 중 비용의 최솟값을 계산하기
가짜 문제 정의하기
D[i][j] = i~j 번 파일을 하나로 합치는 최소 비용
진짜 문제를 풀려면?
D[1][k] = 1~k번 파일을 하나로 합치는 최소 비용
점화식 구해보기
공통점끼리 묶어내는 파티셔닝을 먼저 적용해봅시다.
마지막으로 행위가 같은 경우의 수 끼리 묶어볼 수 있습니다.
요소간의 구간을 나누는 것이 기준이 되기 때문에 항상 전체 길이의 -1 만큼 구간이 발생합니다.
파일의 총량 계산이 필요해진다!
점화식을 채울 때마다 총량 계산을 진행해도 되지만 누적합 테크닉을 사용해서 전처리를 미리 진행합니다.
Sum[i][j] = i번~j번 파일의 총합 = Sum[i][j-1] + a[j]
int[][] sum = new int[K+1][K+1];
sum[0][0] = sizes[0];
for(int i=1; i<=K; i++){
sum[i][i] = sizes[i];
for(int j=i; j<=K;j++){
if(j==1) continue;
sum[i][j] = sum[i][j-1]+sizes[j];
}
}
D 배열을 채워 나가는 순서
시작하는 구간과 끝나는 구간이 정의되는 D 배열의 경우 채워나가는 순서가 중요합니다. 기존의 문제들은 첫행부터 차례대로 채워나가지만, 해당 문제는 다른 순서를 적용해야합니다.
d[1][4]을 채우기 위해서는 d[1][1] 와 d[2][4]가 필요합니다. 즉 첫행부터 채워지면 필요한 부분 문제의 정답을 가져올 수 없습니다.
dp에서는 항상 짧은 구간부터 풀어나가는 것을 원칙으로 합니다. 해당 문제도 구간의 길이가 짧은 문제들을 먼저 풉니다.
for len = 1~k
for i = 1 ~ (k-len+1)
for j = i + len-1
for(int length =2; length<=K; length++ ){
for(int i=1; i<=K-length+1; i++){
int j = i + length-1;
d[i][j] = Integer.MAX_VALUE;
for(int k=i; k<j; k++){
d[i][j] = Math.min(d[i][j], d[i][k]+d[k+1][j]+sum[i][j]);
}
}
}
전체 코드는 다음과 같습니다.
int K = Integer.parseInt(buffer.readLine());
int[][] d = new int[K+1][K+1];
int[] sizes = new int[K+1];
tokens = new StringTokenizer(buffer.readLine());
for(int i=1; i<=K; i++){
sizes[i] = Integer.parseInt(tokens.nextToken());
}
int[][] sum = new int[K+1][K+1];
sum[0][0] = sizes[0];
for(int i=1; i<=K; i++){
sum[i][i] = sizes[i];
for(int j=i; j<=K;j++){
if(j==1) continue;
sum[i][j] = sum[i][j-1]+sizes[j];
}
}
for(int length =2; length<=K; length++ ){
for(int i=1; i<=K-length+1; i++){
int j = i + length-1;
d[i][j] = Integer.MAX_VALUE;
for(int k=i; k<j; k++){
d[i][j] = Math.min(d[i][j], d[i][k]+d[k+1][j]+sum[i][j]);
}
}
}
result.append(d[1][K]).append("\n");