8. Dynamic Programming(동적 계획법) ㅣ최장공통부문자열(LCS) 문제

Dynamic Programming (동적 계획법) ?

 Divide＆conquer(분할정복)와 유사하게, 문제를 여러 작은 문제로 나누어 재귀적으로 해결하는 방법이다.

차이점은 큰 문제의 해답이 작은 문제의 해답들의 식으로 표현되는데, 그 답을 필요할 때마다 재귀적으로 얻는 것이 아니라, 분할된 문제의 해답을 기록해 놓은 후 재사용한다! → ★시간 단축에 매우 유리

---

최장공통부문자열(LCS) 문제 by Dynamic Programming

○ 최장공통부문자열(LCS) 문제 ?

→ 대표적인 유명한 DP문제로, 두 문자열 X, Y의 공통 부문자열 중에서 길이가 가장 긴 것을 찾는 문제

 

     ❕ 부문자열(subsequence)는 문자열에서 몇 개를 지우고 남은 문자의 열을 의미한다.

     ex) X = ABCBBDA 일때, X의 부문자열은 AB, ABB, ABD, BCBD 등 다양하다. 이때, ABBC는 부문자열이 아니다.

 

     ❕ 공통부문자열은 두 문자열에 모두 포함된 부문자열을 의미한다.

     ex) X = ABCBBDA , Y = BDCAD 일때, 공통 부문자열은 BD, BDA, AD, CA 등 다양하다.

---

최장공통부문자열(LCS) 길이 문제에 대한 DㆍP 알고리즘 4단계 분석

 ※Dynamic Programming 알고리즘의 4단계

더보기

 

※ 두 입력 문자열을 X = X1 … Xn , Y = Y1 … Ym라 할때,

 

1. 부문제(subproblem)로 분할

 → i<=n, j<=m인 모든 len_LCS(i, j)를 계산하는 문제가 자연스럽게 부문제가 됨

 

2. 부 문제의 해답을 조합해 큰 문제를 해결하는 식

  1. 핵심은 Xi = X1 ... Xi , Yj = Y1 ... Yj 의 마지막 두 문자 Xi, Yj이다.

  2. Xi == Yj 라면, 이 문자는 LCS에 포함된다 .
    포함된다면, LCS_len(i, j) = LCS_len(i-1, j-1) + 1이 된다

  3. 하지만 Xi != Yj 라면, 둘 중 최소 하나는 LCS에 포함될 수 없다. 어느 문자가 포함되지 않는지 모르겠지만,

     포함되지 않았을 때, 더 긴 LCS를 주는 문자를 골라내면 된다. (우리는 최장길이를 구하고 있기 때문)

 

   ◼ Xi 가 포함되지 않는 경우 : LCS_len(i, j) = LCS_len(i-1, j)
   ◼ Yj 가 포함되지 않는 경우:  LCS_len(i, j) = LCS_len(i, j-1)

❕ 위의 두 경우 중 더 긴 값을 택해야 하므로: LCS_len(i, j) = max(LCS_len(i-1, j), LCS_len(i, j-1))

  

3. 테이블에 저장하기 

  → 가로 : (n x 1), 세로 : (m + 1) 의 크기를 가진 이차원 리스트를 len을 준비한다
  → len[i][j]를 계산하기 위해선, Xi == Yj 와 Xi != Yj 결과에 따라 len(i-1, j), len(i, j-1), len(i-1, j-1)이 필요하다.

     따라서, i, j가 점점 커지는 방향으로 이차원 리스트를 순서대로 채우면 된다.

---

그림으로 알아보기

X = ABCBDAB, Y = BDCABA 일때,

 

우선, i 나 j가 0이면 공통부문자열이 없기 떄문에 0을 채워넣는다.

len[i][j]를 계산하기 위해선 위해 말했듯이

len(i-1, j), len(i, j-1), len(i-1, j-1)이 필요하기 떄문에 i, j가 점점 커지는 방향인 위부터 빨간색 화살표 방향으로 하나하나씩 채워준다. 

 

 

 

Xi == Yj 일때는 len[i][j] = len[i-1][j-1] + 1

Xi != Yj 일때는 len[i][j] = max(len[i-1][j],len[i][j-1])의 식으로 정한 순서대로 채우면,  테이블이 완성된다.

 

완성된 테이블

우리가 원하는 최장 공통 부문자열의 길이는 곧 len[X의 길이][Y의 길이] 이므로,

X, Y의 최장 공통 부문자열의 길이는 len[7][6], 4 이다

---

 

그렇다면, LCS 자체를 알 수는 없을까?

 

▷LCS는 len 테이블을 역추적하면 알 수 있다.

 

 

 

최종목표였던 len[7][6]은 len[7][5] 혹은 len[6][6]에서 온 것이기 때문에, Xi != Yj일때이다.

둘 중 어느방향으로 추적을 해도 상관이 없다.

len[6][6]로 거슬러 올라가보겠다 .

 

 

 

                                 ↓

 

거슬러 올라간 len[6][6]은 Xi == Yj 일때 이므로 

 len[5][5]에서 온 것이다. 

고로 X6 == Y6으로 공통 부분 문자열이다 .

공통부분 문자열인 부분은 ✔ 해두겠다.

이 방식으로 더이상 거슬러 올라갈곳이 없을때까지 거슬러 올라가보면,

 

 

                                 ↓

 

 

이 와 같은 결과가 나온다. 

 

왼쪽에서부터 ✔ 된 부분을 문자열로 합치면

BCBA로, X와 Y의 LCS를 구할 수 있다.

 

 

 

 

---

※ python code

x = input()
y = input()
find_LCS = ''
def LCS(i,j) :
    global find_LCS

    #len리스트 구하기
    L = [[None]*(j+1) for _ in range(i+1)]
    for k in range(i+1) :
        for s in range(j+1) :
            if k == 0 or s == 0 : 
                L[k][s] = 0
            elif x[k-1] == y[s-1] :
                L[k][s] = L[k-1][s-1] + 1                
            else :
                L[k][s] = max(L[k-1][s], L[k][s-1])
    
    #LCS 자체를 구하기
    while i !=0 or j != 0 :
        if L[i-1][j] == L[i][j] :
            i -= 1
        elif L[i][j-1] == L[i][j] :
            j -= 1
        else :
            find_LCS += x[i-1]
            i -= 1
            j -= 1
    return L[len(x)][len(y)]

print(LCS(len(x),len(y))) #공통부문자열 길이

find_LCS = list(find_LCS)
find_LCS.reverse()
print("".join(find_LCS)) #LCS자체

---

[출처]

신찬수 교수 (한국외국어대학교 컴퓨터 공학부), ‘알고리즘 - Algorithm with Python’, p.87~89

-Youtube : ‘Chan-Su Shin’

Chan-Su Shin