Dynamic_Programming-LCS(Longest Common Subsequence)
대표적인 유명 DP 문제이다.
Bioinformatics 수업에서도 두 염기서열이 얼마나 가까운지를 구하기 위한 방법으로 배웠었고 전형적인 DP 문제이기 때문에 확실하게 이해하는 것이 좋다고 한다.
문제 : 두 문자열 X, Y의 공통 부문자열 중에서 길이가 가장 긴 것을 찾는 문제다.
-
부문자열(Subsequence) : 문자열에서 몇 개를 지우고 남은 문자의 열을 의미함.
-
LCS는 하나 이상일 수도 있다.
표기
-
입력 문자열
X = x1 ... xn
Y = y1 ... ym -
Prefix
Xi = X1 ... Xi
Yi = Y1 ... Yi -
LCS(i,j) = Xi와 Yj의 LCS
-
len(i,j) = |LCS(i,j)| = Xi와 Yj의 LCS 길이
X
DP의 4단계 분석을 적용해보자.
1. 큰 문제 -> 작은 문제로 분할
해를 분석해서 부문제로 분할하기.
-> LCS(i,j) 계산
2. 큰 문제 해 = 작은 해의 점화식
부문제의 해로 큰 문제의 해를 표현 (점화식)
DP 테이블에 들어가 있음.
->
xi == yj )
LCS(i,j) = LCS(i,j) + xi (혹은 yj), len(i,j) = len(i-1, j-1) + 1
가장 마지막 두 문자 (xi, yj)가 서로 같다면 공통 부문자열의 가장 마지막 문제로 당연히 뽑을 것이다.
xi != yj )
Xi 중 가장 마지막 문자(xi)와 Yj 중 가장 마지막 문자(yj)가 정답에 가장 마지막 문자로 뽑힐 수도 있고 안 뽑힐 수도 있다. 하지만 둘 다 뽑히는 경우는 절대로 없다. 따라서 정리하면 다음과 같다.
xi가 포함되지 않는 경우라면, LCS(i,j) = LCS(i-1,j) , len(i,j) = len(i-1, j)
yj가 포함되지 않는 경우라면, LCS(i,j) = LCS(i,j-1), len(i,j) = len(i,j-1
가장 긴 값을 선택해야 하니까
len(i,j) = max(len(i-1,j), len(i,j-1))
가장 마지막 두 문자 (xi, yj)가 서로 같다면 공통 부문자열의 가장 마지막 문제로 당연히 뽑을 것이다.
3. DP테이블 정의 계산
적당한 순서로 DP Table 채우기.
1.이차원 리스트를 준비
- len[i,j]를 계산하려면 xi == yj, xi != yj 여부에 따라 다음 3가지 경우 중 하나의 값이 필요하다.
len(i-1,j)
len(i,j-1)
len(i-1,j-1)
i,j가 점점 커지는 방향으로 이차원 리스트를 채우면 된다. (코드로 구현시 이중 for loop를 돌리면 될 것 같다.)
*LCS 구하기
값이 모두 채워진 DP Table인 len의 가장 마지막 원소인 len[i][j]에서 시작하여 역추적해서 알 수 있을 것이다.
Table을 채우는 과정에서 xi==yj인 경우에 대한 인덱스에 대해서 따로 표시를 해두고 LCS를 구하기 위해 len [i][j]로 부터 추적할 때 앞서 해둔 표시를 만났을 때 해당 글자를 어딘가에 적어놓는 방식으로 i 혹은 j가 0이 나올 때까지 반복 후 모두 적힌 글자를 다시 역순으로 재배열하는 방식으로 찾을 수 있을 것 같다.
4. 정확성 증명
DP Table에서 오리지날 문제의 해 계산하여 알고리즘의 Correctness를 증명.
알고리즘 - 동적계획법 - LCS 문제
https://www.youtube.com/watch?v=EAXDUxVYquY
해당 게시글의 내용은 한국외국어대학교 컴퓨터공학부 신찬수 교수님의 Algorithm 강의의 강의 교재를 통해 배우고 정리한 내용들을 기반으로 작성하였다.
