[기말] DP
DP는 Dynamic Programming, 동적 프로그래밍을 의미한다.
'동적'이라는 말이 들어가서 뭔가 움직일 것 같은 느낌이 있는데, 딱히 그런건 없다.
기본적인 DP 방식은, 문제를 작은 여러개의 문제로 나눈 뒤,
작은 문제들의 값을 이용해 원래 문제의 값을 찾아가는 일종의 Bottom-up 방식의 알고리즘이다.
Dynamic Programming의 대표적인 문제들로는
- Floyd-Warshall
- Matrix Chain Multiplication
- Minimum Edit Distance
- 0-1 Knapsack
- Coin Change
와 같은 문제들이 있다.
이 글에서는 이 5문제들에 대해 알아볼 것이다.
1. Floyd-Warshall
Floyd-Warshall 알고리즘의 이름은 개발자(?)들의 이름이고, 이 알고리즘이 하는 역할은 '전체 쌍 최단거리' 문제이다.
가중치를 가진 그래프에서 각 정점간의 거리들을 모두 계산하는 알고리즘이고, 네트워크나 지도 길 찾기등에 사용된다.
알고리즘의 방식에 대해 작은 그래프와 함께 알아보자.
1. 먼저, 초기값으로 인접한 간선들과의 거리를 가지는 2차원 배열을 만든다.
이 때, 접하지 않은 간선들의 거리는 INF, 자신과의 거리는 계산하지 않는다.
| 출발 지점 | ||||||
| 도착지점 | 1 | 2 | 3 | 4 | 5 | |
| 1 | 0 | 2 | 1 | INF | INF | |
| 2 | 4 | 0 | INF | 4 | -3 | |
| 3 | 3 | INF | 0 | -2 | 2 | |
| 4 | INF | 3 | INF | 0 | INF | |
| 5 | INF | INF | 1 | INF | 0 | |
2. 노드 x에서 노드 y로 이동할 때, k번 노드를 경유하는 경우에 대해 계산한다. (x, y, k = 1 ~ 5)
그리고 경유하는 경우의 거리와 직통으로 가는 거리 중 짧은 것을 선택한다.
예를 들어, 2번 노드에서 3번으로 갈때 1번노드를 통하면 2+3, 직통으로 가면 INF이므로 더 짧은 5가 선택된다.
모든 경우의 수를 탐색해야 하므로
- 1번 노드에서 2,3을 경유해서 가는 경우
- 2번 노드에서 1,4를 경유해서 가는 경우
- 3번 노드에서 1,5를 경유해서 가는 경우
- 4번 노드에서 2,3을 경유해서 가는 경우
- 5번 노드에서 2,3을 경유해서 가는 경우
를 모두 조사해서 2차원 거리 배열을 업데이트 한다.
이 과정을 코드로 나타내면 다음과 같다.
// Floyd-Warshall
for(int node = 1 ; node < matrix.length ; node++) {
for(int layover = 1 ; layover < matrix.length ; layover++) {
if(layover == node) continue; // 경유노드가 출발노드와 같으면 안된다.
for(int endNode = 1 ; endNode < matrix.length ; endNode++) {
if(endNode == node || endNode == layover) continue; // 도착노드가 출발노드나 경유노드와 같으면 안된다.
long layoverDist = matrix[layover][node] + matrix[endNode][layover]; // 경유해서 가는 거리
long directDist = matrix[endNode][node]; // 직통으로 가는 거리
long min = Math.min(layoverDist, directDist); // 두 거리 중 짧은 쪽을 선택
matrix[endNode][node] = (int) min;
}
}
}이를 이용해 위의 그래프의 모든 쌍 최단거리를 구해보면 다음과 같다.
위의 표에서 변한 값(더 짧은 거리를 발견한 값)은 초록색으로 표시해보겠다.
| 출발 지점 | ||||||
| 도착지점 | 1 | 2 | 3 | 4 | 5 | |
| 1 | 0 | 2 | 1 | -1 | 1 | |
| 2 | 1 | 0 | -2 | -4 | -4 | |
| 3 | 3 | 1 | 0 | -2 | -2 | |
| 4 | 7 | 3 | 5 | 0 | 0 | |
| 5 | 4 | 6 | 1 | -1 | 0 | |
이런 알고리즘이 Floyd-Warshall이다.
시간 복잡도는 위의 코드를 보면 알 수 있듯이, matrix의 크기만큼 for문을 3번 돌리므로, O(N^3)이다.
2. Matrix Chain Multiplication
이것은 번역해보면 행렬 곱셈 알고리즘이다.
이 알고리즘의 필요성에 대해 설명하려면 먼저 행렬과 행렬 곱에 대해 알아야한다.
먼저 행렬은 2차원 배열 같은 것이다.
대충 이렇게 생겨먹은 것인데, Row(행, 가로)의 개수와 Column(열, 세로)의 개수를 통해 행렬의 크기를 정한다.
예시의 행렬의 크기는 행이 6개, 열이 5개 있으므로 6x5 행렬이다.
행렬에 대해 알았으니, 행렬곱에 대해 알아보자.
행렬곱에서는 좌측항 행렬의 행의 모든 항과 우측항 행렬의 열의 모든 항을 각각 곱한 값을 모두 더한값이 결과 행렬 항의 값이 된다.
말로 써두면 대체 뭔 개소린가 싶으니 그림으로 살펴보자.
위의 사진과 아래의 그림을 보고 행렬곱을 계산해보면
- r1,1은 A1,1 * B1,1 + A2,1 * B1,2 + A3,1 * B1,3 = (1*1) + (2*3) + (3*5) = 22
- r1,2는 A1,1 * B2,1 + A2,1 * B2,2 + A3,1 * B2,3 = (1*2) + (2*4) + (3*6) = 28
- r2,1은 A2,1 * B1,1 + A2,2 * ....
이런 방식이다. 아무튼 중요한건 이게 아니니까 대충 이정도에서 스킵하고,
행렬 곱의 방식을 통해 우리가 알 수 있는 사실은
1. 행렬 A,B를 곱하기 위해서는 행렬 A의 열의 수와 행렬 B의 행의 수가 같아야한다. ( 사진에서 k를 공유 )
2. 행렬 A,B를 곱한 결과는 '행렬 A의 행의 수 * 행렬 B의 열의 수'크기의 행렬이 나온다. (m * n)
3. 행렬 A * 행렬 B를 계산하기 위해서는 m*k*n번의 곱셈 연산을 수행해야한다.
이다.
행렬 두 개, 세 개 정도만 곱한다면 별로 문제가 되지 않겠지만, 행렬을 5개 6개, 수십개 이렇게 계산한다면,
결과 행렬을 최대한 작게 만들면서 계산해야 곱셈 연산의 수를 최소화 할 수 있을 것이다.
예를 들어, A(10x20) * B(20x5) * C(5x15)를 계산할 때, A*B가 먼저라면 1750회, B*C가 먼저라면 4500회의 곱셈이 필요하다. 이러한 차이가 누적되면 나중에는 수십만, 수백만회의 곱셈연산 횟수의 차이가 발생할 것이다.
이러한 일을 방지하기 위해 곱셈 연산의 횟수를 최소화하기 위한 알고리즘이 필요했고 그게 이 행렬곱 알고리즘이다.
행렬곱 알고리즘에서는 Bottom-up 방식을 사용하는데, 예를 들어 A*B*C*D라는 행렬곱 식이 있다면,
(A*B), (B*C), (C*D)의 횟수를 적고,
(A*B)*C 와 A*(B*C)를 비교하고 B*(C*D)와 (B*C)*D를 비교하고...
(A*B)*(B*C)와 (A*B*C)*D, A*(B*C*D)를 비교하고..
이런 과정을 반복하는데, 중복된 계산을 여러번 하지 않기 위해 이 값들을 배열에 저장한다.
이 과정은 다음과 같다.
| 0 | A*B | (A*B)*C vs A*(B*C) |
(A*B*C)*D vs (A*B)*(B*C) vs A*(B*C*D) |
| 0 | B*C | (B*C)*D vs B*(C*D) |
|
| 0 | C*D | ||
| 0 |
여기서 괄호 안에 있는 값들은 수학적으로 먼저 계산한다는 의미도 있지만,
동시에 배열에 이미 존재하는 값이라는 의미이기도 하다.
아무튼 (10x20) * (20x5) * (5x15) * (15x30)의 횟수를 구하는 코드를 구현해보면 다음과 같다.
// 곱할 때 중복되는 수들은 하나로 묶어도 문제 없다.
int[] matrices = new int[] {10, 20, 5, 15, 30};
// 결과 초기화
int numOfMatrices = matrices.length - 1;
int[][] results = new int[numOfMatrices][numOfMatrices];
// (i,i)는 Ai*Ai의 횟수를 의미한다. 0으로 초기화
for (int i = 0; i < numOfMatrices; i++) {
results[i][i] = 0;
}
// diagonal은 부분문제의 크기를 의미한다.
// diagonal = 1은 A*B, B*C, C*D
// diagonal = 2는 A*B*C, B*C*D ...
for (int diagonal = 1; diagonal < numOfMatrices; diagonal++) {
// i는 곱셈에서 가장 왼쪽에 위치하는 행렬을 의미한다.
// i=0 -> 행렬 A, i=1 -> 행렬 B ...
for (int i = 0; i < numOfMatrices - diagonal; i++) {
// j는 곱셈에서 가장 오른쪽에 위치하는 행렬을 의미한다.
// diagonal = 1, i = 0이면 A*B 이므로 j는 B를 가리킨다.
// diagonal = 2, i = 1이면 B*C*D 이므로, j는 D를 가리킨다.
int j = i + diagonal;
// 행렬곱 횟수를 최대치로 둔다.
results[i][j] = Integer.MAX_VALUE;
// i~j까지의 행렬들을 이용해 만들 수 있는 모든 조합에 대해 계산한 후,
// 그 최소 값을 results[i][j]에 저장한다.
// diagonal = 1, i = 0이면 A*A + B*B + A*B 를 계산한다.
// diagonal = 2, i = 0이면
// 1. A*A + B*C + A*(B*C)
// 2. A*B + C*C + (A*B)*C 순서로 계산한 후 최소값이 저장된다.
for (int k = i; k < j; k++) {
int temp = results[i][k] + results[k+1][j] + dimensions[i]*dimensions[k+1]*dimensions[j+1];
if (temp < results[i][j]) {
results[i][j] = temp;
}
}
}
}코드가 좀 복잡할수도 있어서 예시를 주석으로 자세하게 작성해보았다.
MatrixChain 알고리즘의 시간복잡도는
- 초기화 O(N)
- 부분문제의 수 : N-1
- 부분문제의 연산 수 : O(N^2)
이므로, O( (N^2)(N-1) + N) = O(N^3)이다.
3. Edit Distance
편집거리문제는 문자열 2개를 두고, 문자열 A가 B로 바뀌려면 삽입, 삭제, 변경을 총 몇번해야하는지를 구하는 문제이다.
예를 들어,
- String -> Sting으로 하려면 r만 삭제하면 되니까 Edit Distance는 1이다.
- String -> Strong 또한, i->o로 변환만 하면 되니까 Edit Distance는 1이다.
- Str -> Strong은 ong을 추가해야하므로, Edit Distance는 3이다.
- Strong -> Stone는 r을 삭제하고 g를 e로 변경하면 되므로, Edit Distance는 2이다.
사실 마지막 예시같은 경우를 위해 필요한 알고리즘이다.
'가장 최소한의 횟수로' 해야 하기 때문에...
이 알고리즘을 수행할 때에는 각 문자열을 공백 상태부터 한 글자씩 늘려가면서 횟수를 비교하는 방식을 이용한다.
'-'를 공백 문자라고 생각하면 다음과 같다.
| - | s | t | r | |
| - | '-' => '-' | '-' => s | '-' => st | '-' => str |
| s | '-' => s | s => s | st => s | str => s |
| o | '-' => so | s => so | st => so | str => so |
| c | '-' => soc | s => soc | st => soc | str => soc |
| k | '-' => sock | s => sock | st => sock | str => sock |
이러한 2차원 배열을 구성하게 되는데, 여기서 공백-> 각 문자로 가는 0행이나 0열은 초기값으로 만든다.
그리고 직접적인 Edit Distance를 구하기 위한 1~4행, 1~3열은 다음과 같은 규칙으로 진행한다.
- 위 값에서 글자 하나를 추가+변환해서 오는 경우 : arr[y-1][x] + 1
- 왼쪽 값에서 글자 하나를 추가+변환해서 오는 경우 : arr[y][x-1] + 1
- 문자를 추가했지만, 해당 위치 문자가 똑같아서 변환할 필요가 없는 경우 : arr[y-1][x-1]
예를 들어 위 표의 [1,1]의 경우
- '-' => 's'가 되기 위해 s를 추가했고, 이 s를 변환해서 맞추는 경우 : 2
- '-' => 's'가 되기 위해 s를 추가했고, 이 s를 변환해서 맞추는 경우 : 2
- '-'에서 s를 추가했는데, str과 sock의 첫 문자가 s로 똑같으니 변환이 필요없는 경우 : 1
에서 가장 작은 값인 1을 선택해 [1,1] = 1이 된다.
결과적으로 표는 이런 형태가 된다.
| - | s | t | r | |
| - | 0 | 1 | 2 | 3 |
| s | 1 | 0 | 1 | 2 |
| o | 2 | 1 | 1 | 2 |
| c | 3 | 2 | 2 | 2 |
| k | 4 | 3 | 3 | 3 |
str->sock를 위해 3번의 편집거리가 필요하다.
이를 구현하는 코드는 다음과 같다.
// 두 개의 문자열을 가져온다.
char[] charArray1 = string1.toCharArray();
char[] charArray2 = string2.toCharArray();
// dp 배열 초기화
int[][] dp = new int[charArray1.length+1][charArray2.length+1]
for(int s1 = 0 ; s1 <= charArray1.length ; s1++) {
dp[s1][0] = i;
}
for(int s2 = 0 ; s2 <= charArray2.length ; s2++) {
dp[0][s2] = s2;
}
// 편집 거리 구하기
for(int s1 = 0 ; s1 < charArray1.length ; s1++) {
for(int s2 = 0 ; s2 < charArray2.length ; s2++) {
if(charArray[s1] == charArray[s2]) { // 같은 위치의 문자가 같은 경우
dp[s1+1][s2+1] = dp[s1][s2]
} else { // 같은 위치의 문자가 다른 경우
// 왼쪽, 왼쪽 위, 위 3개 중 가장 작은 수에 1을 더한 값
dp[s1+1][s2+1] = getMin(dp[s1][s2+1], dp[s1+1][s2], dp[s1][s2]) + 1;
}
}
}
return dp[charArray1.length][charArray2.length];
///
int getMin(int... nums){
int min = Integer.MAX_VALUE;
for(int n : nums) {
if(min > n) min = n;
}
return min;
}시간 복잡도는 '문자열 1의 길이 * 문자열 2의 길이'만큼 반복하므로,
O(MN)이다.
4. 0-1 Knapsack
0-1 Knapsack문제는 한국어로는 배낭문제라고 주로 부르는 것 같다.
n개의 물건에 대해 각각 무게와 가치가 주어지고, 배낭에는 최대 무게가 정해져있을때,
배낭에 최대한 높은 가치로 물건을 담는 경우의 수를 구하는 문제이다.
이 경우, 배낭의 최대 용량을 0부터 1씩 늘려가면서 최선의 경우를 구하게 되는데,
각 물건에 대해 '용량을 1씩 늘리면서 담아온 경우의 가치' vs '이 물건의 무게만큼 짐을 빼고 이 물건을 넣었을때의 가치' 를 비교해서 최대 가치를 찾아내는 방식이다.
간단한 예시를 들어보면, 가치가 25이고 무게가 2인 보석A와 가치가 40이고 무게가 3인 보석 B가 있다고 해보자.
배낭의 최대 용량은 3이다.
| 배낭의 용량 | 0 | 1 | 2 | 3 |
| 보석A | 0 | 0 | 25 | 25 |
| 보석B | 0 | 0 | 25 | 40 |
대충 이러한 표가 그려지는데,
[3, 보석B]에서는 [3,보석A]와 '[3-보석B의 무게, 보석B] + 보석B의 가치'를 비교 했을 때,
25 vs 0+40 에서 0+40이 더 크므로 이쪽이 선택됬다고 보면된다.
이러한 방식을 코드로 작성해보면 다음과 같다.
int maxWeight; // 배낭의 최대 무게
Item[] items; // 물건의 종류 ( weight : 무게, value : 가치 )
//물건을 넣지 않는 경우와 각 물건을 넣는 경우가 필요하므로 items.length+1
//무게 0부터 maxWeight까지 모두 필요하므로 크기는 maxWeight+1
int[][] dp = new int[items.length+1][maxWeight+1];
for(int item = 0 ; item < items.length ; item++) {
int dp_y = item+1;
for(int weight = 0 ; weight <= maxWeight ; weight++) {
// 이전 물건이 가방에 들어가 있는 경우로 설정
dp[dp_y][weight] = dp[item][weight];
Item itemInfo = items[item];
if(weight >= itemInfo.weight) {
// 이전 물건이 그대로 들어있는 경우와, 현재 탐색중인 물건을 넣었을 때의 가치를 비교하여
// 큰 값을 저장한다.
dp[dp_y][weight] = Math.max(dp[dp_y][weight], dp[item][weight - itemInfo.weight] + itemInfo.value);
}
}
}
return dp[items.length][maxWeight];배낭 문제의 시간 복잡도는 '물건 개수 * 배낭의 무게'만큼 계산하므로
O(NM) 이다.
5. Coin Change
Coin Change는 거스름돈을 줄 때, 최소 동전의 개수를 구하는 알고리즘이다.
일반적으로 동전을 거슬러주는 최소 개수 알고리즘을 Greedy로 많이 하는데,
동전의 단위가 일정하지 않다면, 이런 방식은 최적해를 도출하지 못할 수 있다.
그래서 1원부터 거슬러주는 모든 경우의 수를 탐색하여 최적해를 도출하는 알고리즘이다.
예를 들어 동전의 종류가 1, 5, 10, 16 이 있다고 해보자.
1,2,3,4원을 거슬러 줄 때는 줄 수 있는 가장 높은 동전은 1원이므로, 각각 1,2,3,4개씩 된다.
5원을 거슬러 줄때는 1원 5개로 주는 방법과, 5원 1개로 주는 방법이 있는데,
이 5원 1개라는 결과는 '0원에서 주는 동전의 개수 + 1개' 로 도출된 결과이다.
10원을 거슬러 줄 때는
- '0원 동전수' + 10원 1개 = 1개
- '5원 동전수' + 5원 1개 = 2개
- '9원 동전수' + 1원 1개 = 6개
이므로 10원 1개로 지급하는 1개가 결과가 된다.
20원을 거슬러 줄 때는
- '4원 동전 수' + 16원 1개 = 5개
- '10원 동전 수' + 10원 1개 = 2개
- '15원 동전 수' + 5원 1개 = 3개
- '19원 동전 수' + 1원 1개 = 5개
로 가장 작은 수인 '10원 동전 2개' 로 2개가 결과가 된다.
이것도 역시 코드로 작성해보면 다음과 같다.
int amount = 20; // 거스름돈 20원의 경우를 계산한다.
int[] dp = new int[amount+1]; // 0~20원을 계산해야 하므로, amount+1
int[] coins = {1, 5, 10, 16}; // 동전의 종류는 1, 5, 10, 16 원이다.
for(int money = 0 ; money <= amount ; money++) {
for(int coin : coins) {
if(coin > money) break; // 동전의 금액이 거스를 돈보다 크면 다음 회차로 넘어간다.
int coinCount = dp[money-coin] + 1; // 동전 단위만큼 뺀 금액의 동전 개수 + 탐색중인 동전 1개
dp[money] = ( dp[money] == 0 ) // 현재 최소 동전 개수가 0이면
? coinCount // 비교 없이 설정한다.
: Math.min(dp[money], coinCount); // 현재 개수 vs 이번 동전을 넣는 경우
}
}
return dp[amount];시간 복잡도는 '동전 개수 * 거스름돈의 크기' 이므로,
O(MN)이다.