알고리즘) 5 DP Examples - Knapsack, LCS, LIS, Edit Distance, Matrix Chain Multiplication

※ 귀찮아도 직접 손으로 쓰고 그리며 생각해야 이해가 빠르다

Example 1 : Knapsack (배낭 문제)

Dynamic Programming

무게와 가치가 정해진 N개의 물건이 있을때, 가치의 총합이 max가 되도록 배낭을 싸는 문제.
이때, 배낭의 무게 제한은 K이다.
(각 물건은 1개씩만 존재하며, 배낭에 넣거나/안넣거나)

동전교환문제와 마찬가지로 Greedy한 방법으로 해결되지않음.

ex)
V[N] = {13,8,6,12}
W[N] = {6,4,3,5}
D[i][j] = i번째 물건까지 넣을지/안넣을지 정했을때, 무게 j이하를 채우는 가치의 합중 최대값
=> 점화식 : D[i][j] = Max(D[i-1][j], D[i-1][j-W[i]]+V[i])

Max에서 비교하는 두 값중, 전자는 이전상태 그대로 i번째물건을 안넣는것을, 후자는 이전상태에서 i번째물건을 넣는것을 의미.

Input	Output
첫 줄에 물건의 개수 N과 배낭의 무게 제한 K가 주어집니다. (1 ≤ N ≤ 100, 1 ≤ K ≤ 10,000) 둘째 줄부터 N개의 줄에 걸쳐 각 물건의 가치 Vi와 무게 Wi가 주어집니다. (1 ≤ Vi, Wi ≤ 10,000)	무게 제한 K안에서 담을 수 있는 물건 가치 총합의 최대값을 출력합니다.

import java.util.*;

public class Test {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int k = sc.nextInt();

        int v[] = new int[n + 1];
        int w[] = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            v[i] = sc.nextInt();
            w[i] = sc.nextInt();
        }

        int d[][] = new int[n + 1][k + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= k; j++) {
                if (j < w[i]) { // 새로운 w[i]무게가 무게제한j보다 크면 어짜피 새로 못넣으므로, 이전값 유지
                    d[i][j] = d[i - 1][j];
                } else { // 아니면 새롭게 넣을수 있으므로, 넣었을때와 안넣었을때 비교해보고 큰값으로.
                    d[i][j] = Math.max(d[i - 1][j - w[i]] + v[i], d[i - 1][j]);
                }
            }
        }

        int ans = 0;
        for(int i = 0; i <= k; i++){
            if(ans < d[n][i]){
                ans = d[n][i];
            }
        }

        System.out.println(ans);
    }
}

---

Example 2 : Longest Common Subsequence (LCS, 최장 공통 부분수열)

Dynamic Programming

LCS : 주어진 수열 모두의 부분수열이 되는 가장 긴 수열

ex)
A={1,2,3,4,5,6}, B={1,3,5,4,2,6}일때, LCS(A,B)는 {1,3,4,6}또는{1,3,5,6}이며 그 길이는 4
A="abaabcd", B="baadca"일때, LCS(A,B)는 "baac"이며 그 길이는 4

방법) LCS[A][B] 테이블을 이용해 길이를 구한다.

* LCS[i][j] : LCS( A[0-i], B[0-j] )의 길이

i ) LCS[i-1][j]에 새롭게 A[i]가 붙여진 경우

B[j]가 이미 이전단계에서 사용되었으므로, A[i]와 공통으로 사용될 B의 문자가 존재하지 않는다.
즉, AB중 한쪽만 증가하였으므로 이전값 그대로 유지.
LCS[i][j] = LCS[i-1][j]

ii ) LCS[i][j-1]에 새롭게 B[j]가 붙여진 경우
위와 같은 이유, 이전값 그대로 유지한다.
LCS[i][j] = LCS[i][j-1]

iii ) LCS[i-1][j-1]에 새롭게 A[i]와 B[j]가 붙여진 경우

즉, AB 양쪽다 길이가 1씩 증가한 경우, 비교할 거리가 생김.

새로 생긴 두 값이 같으면, 성공하였으므로 길이 1 증가.
그외의 경우, 실패하였으므로 이전 값 2개 비교후 유지.

* 이때 인덱스를 0부터 시작하면 복잡해지므로,
1부터 시작해서 A,B의 인덱스는 1~LengthA,B와 같은 형태로 표현한다.

최종 점화식

Input	Output
첫 줄에 문자열 A의 길이 LA와 문자열 B의 길이 LB가 주어집니다. (1 ≤ LA, LB ≤ 1,000) 둘째 줄에 문자열 A, 셋째 줄에 문자열 B가 주어집니다.	두 문자열의 LCS의 길이를 출력합니다.

import java.util.*;

public class Test {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);

        int la = sc.nextInt();
        int lb = sc.nextInt();
        String a = sc.next();
        String b = sc.next();

        int lcs[][] = new int[la + 1][lb + 1];
        for (int i = 1; i <= la; i++) {
            for (int j = 1; j <= lb; j++) {

                if (a.charAt(i - 1) == b.charAt(j - 1)) {
                    lcs[i][j] = lcs[i - 1][j - 1] + 1;
                } else {
                    lcs[i][j] = Math.max(lcs[i-1][j], lcs[i][j-1]);
                }

            }
        }

        System.out.println(lcs[la][lb]);
    }
}

---

Example 3 : Longest Increasing Subsequence (LIS, 최장 증가 부분수열)

Dynamic Programming

증가수열 : 수열A의 원소에 대해 A[i] < A[j] (i<j)가 성립하는 수열
LIS : 가장 긴 증가수열

ex) A={20,1,7,4,5,6,13,3}이라면 LIS(A)={1,4,5,6,13}이며 그 길이는 5이다.
역시 비슷한 방법으로, D[i] 배열을 유지하며 문제 해결. (점점 커지도록)
D[i] : i번째 원소를 마지막으로 갖는 최장증가수열의 길이
=> i보다 작은 j들에 대해, A[j]<A[i]를 만족하는, D[j]들 중 최대값 + 1

점화식 : D[i] = Maxj=0toi-1, A[j]<A[i]( D[j] ) + 1

* D[i]의 결과는 뒤로 갈수록 커지는 형태가 아니다! 따라서 LIS의 길이를 구하려면 D[i]값들 중 가장 큰 값을 찾아야한다.

Input	Output
첫 줄에 원소의 개수 N이 주어집니다. (1 ≤ N ≤ 1,000) 둘째 줄에 각 원소의 값을 나타내는 정수 N개가 주어집니다.	주어진 수열의 LIS 길이를 출력합니다.

import java.util.*;

public class Test {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int a[] = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

        int d[] = new int[n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (a[j] < a[i]) { // a[j]<a[i]은 a[i]가 '추가가능'함을 의미한다
                    if (d[i] < d[j]) { // 조건만족하는 d[j]들중 최대값을 넣는다. 이후 1 더함
                        d[i] = d[j];
                    }
                }
            }
            d[i]++;
        }

        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (ans < d[i]) {
                ans = d[i];
            }
        }

        System.out.println(ans);
    }
}

---

Example 4 : Edit Distance

Dynamic Programming

Edit Distance (편집 거리) :
문자열A에서 문자 삽입,삭제,수정 등을 통해 문자열B로 변경하는데 필요한
최소연산횟수를 구하는 문자열 유사도 판단 알고리즘

D[i][j] : A[1.i]까지 사용해서 B[1,j]까지 만드는데 필요한 최소편집거리

편의를 위해 인덱스가 1부터 시작하도록 설정
i ) D[i-1][j] 상태에서 A[i]를 다룰때 : A[1,i-1]과 B[1,j]는 똑같이 만들어져있으므로, A[i]를 삭제한다.(+1)
ii ) D[i][j-1] 상태에서 B[j]를 다룰때 : A[1,i]과 B[1,j-1]는 똑같이 만들어져있으므로, A에 B[j]를 삽입한다.(+1)
iii ) D[i-1][j-1] 상태에서 A[i]. B[j]를 다룰때 : 두 값이 같으면 패스, 다르면 A[i]를 B[j]로 수정한다.(+1)

최종 점화식

D[i][j]의 값을 3개의 값중 min으로 선택하는 것은,

표에서 보면 D[i][j]값을 결정하는데, 1. 대각선(D[i-1][j-1]자리)방향에서 접근하는 방법이 있고 2. 왼쪽(D[i-1][j]자리)방향에서 접근하는 방법이 있고 3. 위쪽(D[i][j-1]자리)방향에서 접근하는 총 3가지 방법이 있다.

이 세 방법중 가장 효율적인 최소의 횟수를 선택하는 것.

우리가 구하는 값은 A[1,LengthA] => B[1,LengthB]이므로
테이블에서 D[LengthA][LengthB] = D[6][7]을 찾으면 답은 3이다.
* D[i][j] 배열에 변형중인 문자열이 아닌, 그 단계까지의 횟수가 저장됨을 주의하자.

Input	Output
첫 줄에 문자열 A의 길이 LA와 문자열 B의 길이 LB가 주어집니다. (1 ≤ LA, LB ≤ 1,000) 둘째 줄에 문자열 A, 셋째 줄에 문자열 B가 주어집니다.	A를 B로 바꾸기 위한 최소 편집거리를 출력합니다.

import java.util.*;
        import java.lang.*;

public class Test {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);

        int la = sc.nextInt();
        int lb = sc.nextInt();

        String a = sc.next();
        String b = sc.next();

        int d[][] = new int[la + 1][lb + 1];
        for (int i = 1; i <= la; i++) {
            d[i][0] = i;
        }
        for (int j = 1; j <= lb; j++) {
            d[0][j] = j;
        }

        for(int i=1; i<=la; i++) {
            for(int j=1; j<=lb; j++) {

                if(a.charAt(i-1) == b.charAt(j-1)) { // 문자열 인덱스는 0부터 시작하므로 a[i]와 b[j]를 비교하는 것
                    d[i][j] = d[i-1][j-1];
                } else { // 3개의 값중 min 선택
                    d[i][j] = Math.min(
                            Math.min(d[i-1][j], d[i][j-1]),
                            d[i-1][j-1]
                    ) + 1;
                }
                // 점화식을 그대로 구현하고있음
            }
        }

        System.out.println(d[la][lb]);
    }
}

---

Example 5 : Matrix Chain Multiplication

Dynamic Programming

행렬의 곱셈
n*m행렬 A와 m*k행렬 B를 곱하면, A*B=행렬C의 크기는 n*k이고 이를 구하는데 n*m*k번의 곱셈이 수행된다. 이러한 성질로 인해 여러 행렬을 곱할때는 그 순서에 따라 전체 곱셈연산 횟수가 달라진다.

ex) A : 2x3 B : 3x5 C : 5x2 인 행렬이라면
(A*B)*C : (2x3x5)+(2x5x2) = 총50번의 곱셈이 수행된다.
A*(B*C) : (3x5x2)+(2x3x2)= 총42번의 곱셈이 수행된다.

이렇게 여러개의 행렬을 곱할때 최소 곱셈 횟수를 구하는 문제를 다뤄보자.

0

1

2

3

4

D[i][j] : i번째행렬부터 j번째행렬까지 곱하는데 드는 최소 곱셈 횟수
(따라서 D[i][i] = 0, 같으면 하나니까 곱셈필요없어 0)

점화식 : D[i][j] = Mink = i to j-1( D[i][k] + D[k+1][j] + (Ri+Ck+Cj) )

ㄴ i-j 범위의 곱은 (이전단계는 무시하고) 가장 마지막단계에서 보면 i-k범위의 곱 결과인 행렬과 k+1-j범위의 곱 결과인 행렬의 곱으로 표현된다. 따라서 i-k범위의 행렬을 만들기까지 소요된 곱셈횟수와 마찬가지로 k+1~j 곱셈횟수를 더한뒤, 이 둘을 곱하는데 소요되는 Ri+Ck+Cj을 더한다.

ㄴ 단 이때, k를 i - j-1까지 돌리며 여러 경우의 수들 중 최소값을 찾아야 한다. ( 0-4를 찾는다면, 0*(1-4), (0-1)*(2-4), (0-2)*(3-4), (0-3)*4로 총4개의 '마지막 두 그룹을 나누는 경우의수'가 존재하므로 )

이때 구하려는 i,j의 범위는 어떻게 설정해야하는가
행렬곱의 시각에서 볼때, 0-2를 구하려면 0-1과 1-2값을 이미 알아야 한다.
0-3을 구하려면 0, 1-3 값을 알거나 0-2, 3 값을 알아야한다. (from 마지막단계 시각) 물론, 저 1-3값이나 0-2값을 구하는데 또 그 이전 depth값들이 필요하다.
따라서 작은범위부터 점차적으로 증가시키며 i,j값을 구해가야한다. 예를 들어 위와같이 0~4의 경우라면
0-1, 1-2, 2-3, 3-4,
0-2, 1-3, 2-4,
0-3, 1-4,
0-4 순으로 d[i][j]값을 구할것.

Input	Output
첫 줄에 행렬의 개수 N이 주어집니다. (1 ≤ N ≤ 500) 두번째 줄부터 N개의 줄에 각각의 행렬의 크기 R과 C가 주어집니다. (1 ≤ R, C ≤ 500) 이때 i번째 행렬의 R과 i+1번째 행렬의 C는 항상 같음이 보장됩니다.	주어진 행렬 곱셈의 결과를 얻기 위해 필요한 최소 곱셈 횟수를 출력합니다.

import java.util.*;

public class Test {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int r[] = new int[n];
        int c[] = new int[n];
        for (int i = 0; i < n; i++) {
            r[i] = sc.nextInt();
            c[i] = sc.nextInt();
        }

        int d[][] = new int[n][n];

        for (int gap = 1; gap < n; gap++) {
            for (int i = 0; i < n-gap; i++) {
                int j = i+gap; // gap,i,j 인덱스 범위설정은 본문을 참고하자

                // i~j의 최소 calc를 구하자
                d[i][j] = -1;
                for (int k = i; k < j; k++) { // k는 i~j사이 차례대로 돌며, i~k / k+1~j 두 그룹의 곱으로 calc값 구한다
                    int calc = d[i][k] + d[k+1][j] + ( r[i] * c[k] * c[j] ); // r[k]==c[k+1]임
                    if (d[i][j] < 0) { // 처음엔 일단 넣고
                        d[i][j] = calc;
                    } else if (calc < d[i][j]) { // k-for문 돌면서 더 최소인 calc값 나오면 대입
                        d[i][j] = calc;
                    }
                }

            }
        }

        System.out.println(d[0][n - 1]);
    }
}