[알고리즘] 동적 계획법(Dynamic Programming) - 5

동적 계획법(Dynamic Programming) - 5

이번 시간에는 Longest Common Subsequence를 알아보자

Longest Common Subsequence는 줄여서 LCS라고 부르는데, 약어로 부르는것은 그만큼 유명하다는 뜻이다.

입력으로 2개의 문자열이 주어지며, bcdb는 문자열 <abcbdab>의 subsequence이다.

또한 <bca>는 문자열 <abcbdab>와 <bdcaba>의 common subsequence(공통 부분 문자열)이다.

우리가 고려해야할 부분은 LCS인데, 입력으로 2개의 문자열이 주어졌을때, 

common subsequence중에서 가장 긴것을 찾으면 된다.

예를 들어, <bcba>는 <abcbdab>와 <bdcaba>의 LCS가 되는 것이다.

그렇다면 위의 그림에서 x라는 문자열과 y라는 문자열이 입력으로 주어진 문자열이며,

z가 우리가 원하는 최적해라고 할 때, z의 일부분이 어떤 부분에 대한 최적해가 되는 것일까.

만약 이 z라는 문자열의 마지막이 A라면 x에도 포함될 것이며 y에도 포함 될 것이다.

그리고 x의 하늘색을 x', y의 노란색을 y'라고 한다면 z의 보라색은 x'와 y'의 LCS가 된다.

L[i][j]는 입력으로 주어진 X와 Y의 LCS의 길이를 뜻한다.

이때, Xi와 Yj가 같은가 다른가에 따라서 2가지 케이스로 분류된다.

만약 Xi와 Yj가 같다면 Xi와 Yj를 제외한 문자열의 LCS를 구한후 마지막 값인 1을 더해준다.

만약 Xi와 Yj가 다르다면 적어도 둘중 하나는 버려야 한다.

다만 문제는 둘중 누구를 버려야 하는지 알수 없다.

먼저 Xi를 버린다는 것은 Xi를 제외한 X전체와 Y의 LCS를 구한다는 것이고,

Yj를 버린다는 것은 Yj를 제외한 Y전체와 X의 LCS를 구한다는 것이다.

따라서 위의 경우 2의 순환식이 성립한다.

종합적으로 보자면 위와 같이 순환식을 정리할수 있다.

i나 j가 0이라는 것은 문자열의 길이가 0이라는 뜻이므로 LCS의 길이는 0이 된다.

그리고 위에서 봤듯이 Xi와 Yj가 같을때와 다를때, 2개의 경우로 나눠서 생각해야한다.

결과적으로 LCS의 코드는 위와 같다.

출처 : 부경대 권오흠 교수님, 영리한 프로그래밍을 위한 알고리즘