개발 공부 - [동적계획법 (Dynamic Programming)] Dynamic Programming - 5

Longest Common Subsequence

Longest Common Subsequence(LCS)

- <bcdb>는 문자열 <abcbdab>의 subsequence이다.

- <bca>는 문자열 <abcbdab>와 <bdcaba>의 common subsequence 이다.

- Longest common subsequence(LCS)

    common subsequence들 중 가장 긴 것

    <bcba>는 <abcbdab>와 <bdcaba>의 LCS이다

Brute Force

- 문자열 x의 모든 subsequence에 대해서 그것이 y의 subsequence가 되는지 검사한다.

- |x|=m, |y|=n

- x의 subsequence의 개수 = 2m

- 각각이 y의 subsequence인지 검사: O(n)시간

- 시간복잡도 O(n2m)

Optimal Substructure

x             ㅁㅁㅁㅁㅁㅁㅁ[A]ㅁㅁ

                                   ↑

                                   ↓        

y                ㅁㅁㅁㅁㅁㅁ[A]

                                   ↑

                                  /

                                ↓     

LCS z       ㅁㅁㅁㅁㅁㅁ[A]ㅁㅁ

ㅁㅁㅁㅁㅁㅁ는 ㅁㅁㅁㅁㅁㅁ와 ㅁㅁㅁㅁㅁㅁㅁ의 LCS이다.

순환식

L[i, j] : 문자열  X =< x1x2 ··· xi >와 Y =< y1y2 ··· yj >의 LCS의 길이

X [x1] [x2] [      ] [      ] [xi-1] [xi]

                                       ↑

                                       ↓

Y [y1] [y2] [y3] [ ] [ ] [ ] [yj-1] [yj]

- 경우 1: xi = yj

    L[i, j] = L[i  1, j  1] + 1

순환식

L[i, j] : 문자열 X =< x1x2 ··· xi >와 Y =< y1y2 ··· yj >의 LCS의 길이

X [x1] [x2] [      ] [      ] [xi-1] [xi]

                                       ↑둘 중 하나는

                                       ↓버려야

Y [y1] [y2] [y3] [ ] [ ] [ ] [yj-1] [yj]

- 경우 2: xi ≠ yj

L[i, j] = max(L[i  1, j], L[i, j  1])

순환식

L[i, j] : 문자열 X =< x1x2 ··· xi >와 Y =< y1y2 ··· yj >의 LCS의 길이

L[i, j] = 0                                         if i = 0 or j = 0;

          L[i  1, j  1] + 1                        if xi = yj ;

          max(L[i  1, j], L[i, j  1])               otherwise.

※

X = ABCBDAB

Y = BDCABA

동적계획법

int lcs(int m, int n) /* m: length of X, n: length of Y */

{

     for (int i=0; i<=m; i++)

         c[i][0] = 0;

     for (int j=0; j<=n; j++)

         c[0][j] = 0;

     for (int i=0; i<=m; i++) {

         for (int j = 0; j <= n; j++) {

             if (x[i] == y[j])

                 c[i][j] = c[i - 1][j - 1] + 1;

             else    

                 c[i][j] = Math.max(c[i - 1][j], c[i][j - 1]);

             }

         }

     return c[m][n];

}

시간복잡도: Θ(mn)