LCS(Longest Common Subsequence, 최장 공통 부분 문자열)-알고리즘10
1. LCS?
우선 아래 개념부터 확인하고 출발하자.
Subsequence vs Substring
- Substring: 문자열에서 연속된 부분 문자열 ex) abcde-> ace 는 substring 아님. abcde->abc 는 substring
- Subsequence: 문자열에서 연속된 문자열이 꼭 아니어도 되는 부분 문자열 ex) abcde-> ace 도 subsequence
- Common Subsequence: 두 문자열중 공통된 subsequence ex) abcde, bzxchje -> 'bce'
따라서 LCS란, 두 문자열 사이에서, 가장 긴 공통 부분 문자열(Longest Common Subsequence)을 뜻한다.
두 문자열이 주어졌을 때, LCS를 어떻게 찾을까?
2.DynamicProgramming(DP)
두 문자열 X={$x_{1}$,$x_{2}$,$x_{3}$ ... $x_{m}$} , Y={$y_{1},y_{2},y_{3}...y_{n}$} 에 대해 두 문자열의 LCS을 찾자.
1단계: 특성 파악하기
이 문제를 가장 원시적으로 푸는 방법은 X의 모든 부분 문자열을 나열하고 각 부분 문자열이 Y의 부분 문자열인지 검사하고 그 중에서 가장 긴 부분 문자열을 찾는 것이다.
X의 각 부분 문자열은 X의 각 원소들 {$x_{1}$,$x_{2}$,$x_{3}$ ... $x_{m}$} 에 대응된다.
이때, 각 원소들은 부분 문자열에 1)포함될 수도 있고, 2)포함이 안될 수도 있다.
따라서 X는 $2^{m}$개의 부분 문자열을 갖고 있어 이 방법은 수행시간이 지수함수에 비례하게 되므로 긴 문자열에 대해서는 시간이 너무 오래걸린다.
따라서 LCS문제는 다음 이유로 Optimal Substructure(최적 부분 구조 특성)특성을 가진다.
$Z$={$z_{1}$,$z_{2}$,$z_{3}$ ... $z_{k}$}를 X와 Y의 LCS라고 하자. 그럼 다음을 따른다.
- $x_{m}$ =$y_{n}$ 이면, $z_{k} = x_{m}=y_{n}$이고, $Z_{k-1}$은 $ X_{m-1} $와 $Y_{n-1}$의 LCS임을 의미한다.
- $x_{m}$ !=$y_{n}$ 이면, $z_{k} != x_{m}$는 $Z$가 $X_{m-1}$와 $Y$의 LCS임을 의미한다.
- $x_{m}$ !=$y_{n}$ 이면, $z_{k} != y_{m}$는 $Z$가 $Y_{n-1}$와 $X$의 LCS임을 의미한다.
이는 X와 Y의 LCS를 찾을 때, 하나 또는 두개의 부분문제를 살펴봐야 함을 말해준다.
즉, $x_{m}$=$y_{n}$이면, $X_{m-1}$ 과 $Y_{n-1}$의 LCS를 찾아야한다. $x_{m}$ = $y_{n}$을 LCS끝에 붙이면 X와 Y의 LCS를 얻게 된다.
2단계: Overlapping Subproblems(겹치는 부분 문제)
X와Y의 LCS를 찾기 위해서 $X_{m-1}$ 와 Y , X와 $Y_{n-1}$의 LCS를 찾아야 한다.
그런데 이 부분 문제들은 각각 $X_{m-1}$ 과 $Y_{n-1}$의 LCS를 찾는 부분 문제를 가지고 있다. 즉 부분 문제가 자기 자신의 부분 문제를 또 갖고 있다.
c[i,j]를 $X_{m}$ 와 $Y_{n}$의 LCS 길이로 정의한다면, LCS문제는 다음과 같은 점화식을 가진다.i=0 이거나 j=0 이라면, 두 문자열중 길이가 0인 문자열이 있다는 의미이므로 LCS의 길이는 0이 된다.
$X_{m}$ 와 $Y_{n}$ 이 다르면 왜 max(c[i,j-1],c[i-1,j]) 인가?
Optimal substructure:
- 큰 문제:$X_{m}$ 와 $Y_{n}$ 의 LCS
- 부분 문제: $X_{m-1}$ 와 Y의 LCS, $Y_{n-1}$ 와 X의 LCS
부분 문제중 최적의 부분문제를 골라야 한다. 여기서 최적의 부분문제: 이 문제는 '가장 긴' subsequence를 찾는 것이기 때문에 더 긴 문자열(부분문제)이 최적의 부분문제다.
3단계:LCS의 길이 계산
위의 식에 따라, LCS길이를 계산하는 재귀 알고리즘을 만들 수 있다. 아래의 코드는 c[i,j]의 모든 배열 칸에 대해 원소를 삽입 하므로 시간 복잡도는 O(n*m)이다.
LCS(X,Y){ //lcs 찾기 위해 새로운 배열 b생성
for i=0~m:
for j=0~n:
if (i==0 or j==0) :
c[i,j]=0
else if (X[i]==Y[j]):
c[i,j]=c[i-1,j-1]+1 //b[i,j]='↑'
else:
c[i,j]=max(c[i,j-1],c[i-1,j]) //b[i,j]='↖'
}
4단계: LCS구성하기
LCS의 길이를 구하는 코드나 점화식을 보면 LCS의 원소를 찾을 때 마다 오른쪽 아래로 +1을 하며 이동한다.(gif참조)
따라서 LCS를 찾기 위해서는 c[i,j]를 완성한 후 c[i,j]에서 부터 역으로 추적하며 원소를 하나 씩 찾으면 된다.
즉 X[i]==Y[j] 조건이 있을 때마다 새로운 2차원 배열 b에 추적할 기호를 기록해놓고 b[i,j]에서 부터 찾아 나가면 된다.
Find_LCS(b,X,i,j){
if i==0 or j==0:
return
if b[i,j]=='↖' :
Find_LCS(b,X,i-1,j-1)
else if b[i,j]=='↑':
Find_LCS(b,X,i-1,j)
else:
Find_LCS(b,X,i,j-1)
}
3. References
CLRS