Dynamic Programming
DP를 정리해보자
DP란?
Dynamic programming! 동적프로그래밍은 기억하기 프로그래밍이라는 용어를 쓴다.
DP를 공부하고 느낀점으로는, 잘 기억해놨다가 잘 가져다쓰는(점화식 활용) 것이 중요하다!
잘 기억하는 방법 중 하나로 메모이제이션이 있는데 동적 프로그래밍 중 하나이다.
재귀 호출 시, 반복적으로 계산되는 것들의 계산 횟수를 줄이기 위해
이전에 계산했던 값을 저장해두었다가 나중에 재사용하는 방법이다.
DP 적용의 조건 : 최적의 원리
어떤 케이스의 최적해가
그 케이스를 분할한 케이스에 대한 최적해를 항상 포함하고 있으면
최적의 원리가 성립한다.
즉, 점화식 표현이 가능하다.
DP의 대표적 문제 3가지를 알아보자.
- 막대기 자르기
- 최장 공통 부분 수열문제 LCS
- 0/1 배낭문제
막대기 자르기
Q. 하나의 막대기가 있다. 막대기를 자르는데 나오는 조각마다 가격이 다르다.
막대기를 잘라 가장 높은 가격을 만들어라.
| 길이(i) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 길이당 가격(Pi) | 0 | 1 | 5 | 8 | 9 | 10 | 17 | 20 | 20 | 24 | 30 |
예제1) 길이가 4인 막대기 최대 가격은 길이 2인 막대기 두개로 P2+P2 = 10
예제2) 길이가 6인 막대기의 최대가격은 P6 = 17 이다.
알고리즘 풀이
길이가 n인 막대기의 최대가격을 Rn이라 할 때 아래 식이 성립한다.
Rn = max(Pi + R n-i) (i는 1부터 n까지)
즉 i가 1부터 n까지인 값들을 반복하면서 최대값을 찾는다.
R6를 구해보자.
R6 = max(P1 + R5, P2 + R4, P3 + R3, P4 + R2, P5 + R1, P6 + R0)
R6를 구하긴 위해선 R0, R1, R2, R3, R4, R5 값들을 알고 있어야한다.
R5를 구하기위해선 R4도 알아야하는데 피보나치처럼 반복해서 Rn을 계산하는 것을 알 수 있다.
따라서 Rn을 메모리제이션할 수 있다.
Rn을 구하는 소스는 아래와 같다!
int getMaxVal(int[] p, int n){
int[] r = new int[n+1];
for(int i=1; i<=n ; i++){
int max = 0;
for(int j=1; j<= i; j++){
max = Math.max(max, p[j] + r[i-j]);
}
r[i] = max;
}
return r[n];
}
최장 공통부분 수열문제 (LCS)
Q. 두 개의 문자열에서 순서대로 겹치는 문자가 최대 몇 개 인가?
예제) 두개의 문자열
ABCBDAB BDCABA
두 문자열의 순서대로 겹치는 문자의 수는 최대 4개이고 경우의 수는 3가지 이다.
ABCBDAB BDCABA
LCS : BCAB
ABCBDAB BDCABA
LCS : BCBA
ABCBDAB BDCABA
LCS : BDAB
이처럼 앞에서부터 겹치는 것들을 찾아 문자열을 만들 때 가장 긴 것이 LCS이다.
알고리즘 풀이
TIP : DP는 맨 처음부터 순서대로 계산하면서 패턴을 알수 있다.
| 0 | B | D | C | A | B | A | |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| A | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
ABCBDAB의 첫번째 A로만 두번째 문자열 BDCABA와 비교했을때 LCS는 1이다.
(A, BDCA), (A,BDCAB), (A, BDCABA)의 LCS는 1
| 0 | B | D | C | A | B | A | |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| A | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| B | 0 | 1 | 1 | 1 | 1 | 2 | 2 |
표를 구할 때 B, B 처럼 같은 값이 나오면 이전까지의 LCS 길이에 +1을 해준다.
이전까지의 LCS 길이란 대각선 (왼쪽 위) 값을 말한다.
대각선에서 +1하는 것은 두 문자를 비교하기전의 LCS길이에 +1 하는것이다.
(AB, BDCAB) -> (A, BDCA) + 1
| 0 | B | D | C | A | B | A | |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| A | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| B | 0 | 1 | 1 | 1 | 1 | 2 | 2 |
| C | 0 | 1 | 1 | 2 | 2 | 2 | 2 |
(ABC, BDCA)와 같이 각각 마지막 문자가 다른 경우에는 비교한 문자가 포함되어있는 직전 LCS를 가지고온다.
표에서는 위와 왼쪽 값 중에서 큰 값이 오게된다. (LCS는 최대값을 구하는 것이므로 두 케이스에서 최대인 값을 가져온다!)
(ABC, BDCA) -> MAX((ABC, BDC), (AB, BDCA))
따라서 표의 값을 구하는 규칙은
-
문자열[n], 문자열[k]가 같다면 [n, k] == [n-1, k-1] + 1
-
문자열[n], 문자열[k]가 다르면 [n, k] == [n-1, k], [n, k-1] 중 큰 값을 가져온다.
for(int i=1 ; i< str1.length; i++){
max = 0;
table[i][0] = 0;
for(int j=1; j< str2.length; j++){
if(str1[i] == str2[j]){
max = table[i-1][j-1]+1;
table[i][j] = max;
} else {
if(table[i][j-1] > table[i-1][j])
table[i][j] = table[i][j-1];
else
table[i][j] = table[i-1][j];
}
}
}
0/1 배낭문제
Q. 도둑이 보석가게에 배낭을 매고 들어왔다.
배낭 최대 용량은 W이며 보석의 무게와 가치는 다르다. 담을 수 있는 최대 가격은?
최적의 원리 성립 체크 (최적해가 부분 사례의 최적해를 포함하는가?)
집합 A를 n개의 보석 중에서 최적으로 고른 부분 집합이라 하자.
- 집합 A가 n번째 보석을 포함하지 않으면 n-1개 보석들과의 최적의 값과 같다.
- 집합 A가 n번쨰 보석을 포함한다면 n포함 보석들의 총가격은 n-1개의 값에서 n의 가격을 더한 값과 같다.
P[i, w] : i 개의 보석, 무게한도 w일 때 최대 가격
포함하지 않을경우 : P[i, w] = P[i-1, w]
포함할 경우 : max( Vi + P[i-1, w - wi], P[i-1, w])
Vi는 V번째 보석의 값
i번째 보석을 넣었을 때 wi 무게를 넣을만큼의 공간을 확보하고 이전 케이스와 최대값을 비교!
알고리즘 풀이
| 보석 무게(wi) | 값(Vi) | i |
|---|---|---|
| 2kg | 3$ | 1 |
| 3kg | 4$ | 2 |
| 4kg | 5$ | 3 |
| 5kg | 6$ | 4 |
표를 그려보면 아래와 같다.
| i \ w | 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 3 | 3 | 3 | 3 |
| 2 | 0 | 0 | 3 | 4 | 4 | 7 |
(i, w)가 (2, 2)일 때 이미 i=1 보석이 들어가 있다.
i=2 보석이 들어가기 위해선 3kg이 필요한데 가방의 최대무게 w가 2이므로 P[i-1, w]에 해당하여 값은 3이다.
(i, w)가 (2, 4)일 때 i=2 보석이 들어갈 수 있게 되는데
i=1 보석이 들어가 있을 때와 ( P[i-1, w] )
i=2 보석을 넣을 수 있을 만큼의 공간을 확보하고 i=2 보석을 넣었을때 V2 + P[1, 1] 가치를 비교하여 max값을 선택한다!
Vi + P[i-1, w-wi] 이므로 V2 + P[2 - 1, 4 - 3]이다. 표에서 P[1,1] 은 0이므로 V2+0 = 4가 된다.