최장 공통 부분 수열이란?
먼저, 부분 수열이란 순서대로 뽑아서 나올 수 있는 수열들을 의미합니다. 예를 들어 abcdefb의 부분 수열에는 abc, bdf등이 있습니다.
따라서 공통 부분 수열은 두 문자열에서 순서대로 뽑아서 나올 수 있는 공통 부분 수열을 의미합니다. 예를 들의 abcde와 cde의 공통 부분 수열에는 ce, de cde 등이 있습니다.
마지막으로 최장 공통 부분 수열은 두 문자열에서 순서대로 뽑아서 나올 수 있는 가장 길이가 긴 공통 부분 수열이 됩니다. abcde와 cde의 최장 공통 부분 수열은 cde가 됩니다.
DP를 활용하여 LCS 구하기
LCS는 DP를 활용하여 해결할 수 있습니다. 두 문자열 A, B의 LCS를 구한다고 가정하면 DP[i][j]는 A의 i번째까지의 문자와 B의 j번째 문자까지의 LCS 길이를 의미하게 됩니다. 점화식은 다음과 같습니다.
$$ DP[i][j] =
\begin{cases}
MAX(DP[i - 1][j], DP[i][j - 1]) & \quad \text{if } i \neq j\\
DP[i - 1][j - 1] + 1 & \quad \text{if } i = j
\end{cases} $$
1) A의 i번째 문자 != B의 j번째 문자인 경우
두개의 문자는 매칭이 되지 않기 때문에 LCS에 포함이 되지 않습니다. 그렇다면 DP[i][j]의 값은 DP[i - 1][j], DP[i][j - 1]중 큰 값을 선택하게 됩니다. 그 이유는 A의 i번째 문자 혹은 B의 j번째 문자중 하나만 LCS에 포함될 가능성이 있기 때문입니다. i번째 문자와 j번째 문자가 이미 매칭이 되지 않았기 때문에 둘 중에 하나만 LCS에 포함이 될 수 있고 A의 i번째를 포함하여 LCS를 계산한 경우는 DP[i][j - 1]에 계산이 이미 되어 있고 B의 j번째 문자를 포함하여 LCS를 계산한 경우는 DP[i - 1][j]에 저장이 되어 있기 때문에 둘 중에 더 큰 값을 사용하게 됩니다.
2) A의 i번째 문자 == B의 j번째 문자인 경우
두개의 문자가 매칭되었습니다. 그럼으로 해당 문자는 LCS에 포함이 되게 됩니다. DP[i - 1][j - 1]에는 A의 i - 1번째 문자까지와 B의 j - 1번째 문자까지의 LCS의 값이 저장되어 있으므로 여기에 이번에 매칭된 문자를 1 더하여 DP[i][j] = DP[i - 1][j - 1] + 1이 되게 됩니다.
느낀점(?)
LCS를 공부하면서 개인적으로 DP에서 중요한 것은 현재 DP[i][j]를 구하기 위하여 어떤 것들이 영향을 미칠 수 있는지가 중요한 것 같습니다. 또, 미리 계산되어 있는 값들을 어떤 방식으로 최적의 현재 값을 찾는데 활용이 될 수 있는지를 찾아낼 수 있어야하는 것 같습니다.