29. 가장 긴 공통 부분 문자열(LCS, Longest Common Subsequence) 찾기 알고리즘

1. 개요

 LCS는 쉬움.

 DP(Dynamic Programming)으로 접근.

 다른 알고리즘 문제에서 이와 비슷한 유형으로 풀어야 했던 문제가 많음.

 이 문제 풀이에 대한 접근을 어떻게 하는지 알아두고 이해하는 것이 중요.

 재귀적 방식에 대한 해답 -> DP로의 변화

 원리

 (1) if (i == m || j == n) : return 0;

 (2) if X[i] == Y[j] : return 1+LCS( ]i+1, j+1 );

 (3) if X[i] != Y[j] : MAX( LCS( i, j+1 ), LCS( i+1, j ));

 총 3가지 방법

 (1) 일반 재귀적 방법

 (2) DP 재귀적 방법

 (3) DP 반복적 방법

 모든 DP 문제에 대해 위 3가지 방법에 대해서 풀이 가능해야 함. (연습하자)

2. 문제

 길이가 m인 문자열 X[X(1...m)]과 길이가 n인 문자열 Y[Y(1...n)]인 두 문자열이 있다.

 두 문자열의 LCS를 찾아라.

 Ex) X="ABCBDAD", Y="BDCABA"일 때, LCS는 LCS(X,Y) = {"BCBA","BDAB","BCAB"}

3. 출력

3-1) 재귀적 방법 코드

3-2) DP 재귀적 방법 코드

3-3) DP 반복적 방법 코드

3-4) 메인

3-5) 출력

4. 정리

 이 원리를 제대로 알아야 겠다라고 생각한 이유는 이 기법을 응용한 문제가 우리나라 최고 복지의 IT기업의 문제로

출제된 적이 있었다. 하지만 그 때의 난 억지스러운 접근을 했고 결국 아주 소수의 경우에만 풀리는 알고리즘을 작성

했다. 하지만 이번 기회에 이렇게 정확한 접근법을 알아서 나중에 이런 문제가 나왔을 때, 당황하지 않고 바로 떠올려서

사용하자.

 

 추가적인 개선 방법

 (1) 배열 역추적을 통한 공통 문자열 출력하는 방법.

 (2) 서로 전체적인 부분에서의 공통 문자열이 아닌 연속된 공통 문자열 찾기.