알고리즘 LCS 최장공통부분서열

알고리즘 문제를 푸는데, LCS문제가 종종 나와서 이번에 한번 개념을 확실하게 잡고자 글을 적어봅니다.

LCS (Longest Common Subsequence)

두 개의 문자 서열 X,Y가 주어졌을 때, X와 Y에서 공통으로 나타나는 부분 문자 서열을 찾는 알고리즘. 부분 서열의 길이가 최대가 되도록 하는 문자서열을 찾는다.

문제를 푸는 방법?

단순하게 풀기 브루트 포스(Brute-Force Approach)

1. X의 모든 부분 서열에서 Y의 부분 서열인 것의 길이를 구한다음 최댓값을 구한다.
2. X의 부분 서열의 개수는 지수 시간 복잡도를 가진다
3. 따라서 이렇게 푸는 방법은 옳지않다.

X = { x1, x2, x3 … x(m-1), x(m) }
Y ={ y1, y2, y3 … y(n-1), y(n) }
Z = { z1, z2, z3 … z(k-1), z(k) }

이 두 식에서, X(m)과 Y(m)이 같다면,

Zk = Xm = Ym
Z(k-1) = LCS(X(m-1),Y(n-1))

X(m)과 Y(m)이 다르다면,

Zk ≠ X(m) : Z = LCS(X(m-1),Y(n))
Zk ≠ Y(n) : Z = LCS(X(m),Y(n-1))

재귀식으로 만든다면,

1. 종료조건 i = 0 또는 j = 0이면 c(i,j) = 0
2. 재귀조건
   1. xi = yj 이면 c(i,j) = c(i-1, j-1) + 1
   2. xi ≠ yj 이면 c(i,j) = max{c(i,j-1),c(i-1,j)}

동적 계획법 DP

1. 메모이제이션을 이용한 동적 계획법.
2. 하향식 해법에서 상향식 해법으로 전환.

아래의 이미지를 참고하면 이해하기가 쉽다.

다를 경우에는 c(i-1,j) c(i,j-1) 중 큰 값을, 같은 경우에는 c(i-1,j-1) +1 값을 갖는다.