[동적계획법] Longest Common SubSequence

동적계획법(Dynamic Programing)이란?

 

복잡하고 어려운 문제를 작은 단위로 '분할'한 후 다시 '결합'하여 최적의 답을 구하는 방법

동적계획법은 분할된 모든 경우의 수를 검토한다. 

중복되는 경우의 검토 비용을 줄이기 위해 기존의 결과를 저장한다. 

 

 

최장 공통 문자열 ( Longest Common SubSequence; LCS )

 

예제) 주어진 두 문자열의 최장 공통 문자열을 구하라.

 

[ abdcg , bdag ]

 

SubString과 SubSequence 의 차이는 연속적이냐 비연속적이냐의 차이다. 두 문자열의 bd는 SubString이다. 두 문자열의 b , g는 SubSequence이다. 비연속적이지만 순서가 맞다. 

 

한 마디로 LCS는 얼마나 두 문자열이 공통된 순서대로 배치되었는가를 확인하는 알고리즘이다. 문자열이 짧으면 직관으로 알 수 있지만 문자열이 길어진다면 직관으로 확인하기 힘들다. 또한 컴퓨터는 인간과 같은 직관이 없다. 하나씩 분리하면서 LCS를 찾아야 한다. 

 

 

끝에서부터 순서대로 확인해보자.

 

 

1) 

 

문자열A와 문자열B의 끝이 g로 같다. LCS 값 +1 된다.

 

 

2) 

 

 

c와 a는 다르다. 그럼 두 가지 선택이 있다. 문자열A의 포인터를 이동시키거나 문자열B 포인터를 이동시켜야 한다. 둘 다 이동시키면 안 된다. 문자열A의 포인터를 다음 문자로 이동시켰는데 a가 나올 수도 있기 때문이다. 고로, 서로 문자가 다르면 두 포인터 중 하나만 이동한다. 문자열A 포인터를 이동시켜보자.

 

3)

 

d와 a는 다르다. 그럼 다시 두 가지 선택이 존재한다. 공통된 문자를 찾을 때까지 문자열A 포인터만 이동시켜보자.

 

 

4)

 

 

 

찾았다. LCS 값은 +1이 된다. 총 LCS는 2가 된다. 그러나 이는 한 가지 경우의 LCS에 불과하다. 

 

 

 

매번 경우는 3가지로 분리된다 .

 

1) 동일

2) 문자열A 포인터 이동

3) 문자열B 포인터 이동

 

동적프로그래밍의 Top-Down 방식이다. 작은 단위로 분할한 뒤 결합하면서 최적해를 구하는 방법이다. 동적프로그래밍은 모든 경우의 수를 탐색하므로 쓸모없는 탐색을 줄여야 한다. 

 

만약 두 문자가 동일하다면 2)와 3)은 생각하지 않아도 된다. LCS +1이 되고 시작하기 때문이다. 

동일하지 않는 경우, 2)와 3) 중 Max값을 선택해야한다. 

 

 

 

 

 

 

 

이와같이, 두 문자열의 포인터를 이동시켜가며 Top-Down 방식으로 LCS를 구할 수 있다. 이 과정을 이차원 테이블 위에 표현하면 쉽게 LCS를 구할 수 있다. 

 

 

 

 

 

포인터A와 포인터B가 가리키는 문자가 동일하므로 LCS +1이 된다. 두 문자가 동일하므로 포인터를 둘다 움직인다.  

 

 

 

 

 

두 문자가 서로 다르다. LCS는 그대로 1이 된다. 포인터A나 포인터B 중 하나를 선택하여 움직여야한다. 포인터A만 계속 선택하여 움직여보자.

 

 

 

 

문자가 동일하지 않으면 그대로 1이고 동일하면 +1이 된다. 포인터A만 움직였을 때, 최종 LCS는 2가 된다. 그럼 다시 돌아와 포인터B만 움직여보자.

 

 

 

포인터B만 움직였을 때 최종 LCS는 1이 된다. 그럼 포인터A와 포인터B를 번갈아가며 움직여보자.

 

 

포인터A를 c에서 d로 움직인다.

c와 a는 동일하지 않으므로 포인터A나 포인터B 중 하나를 선택하여 움직여야 한다.

포인터B를 a에서 d로 움직인다. 

 

포인터A와 포인터B가 동일한 문자를 가리키므로 LSC는 2가 된다. 두 문자가 동일하므로 두 포인터를 다음 문자로 이동시킨다.

 

 

 

포인터A와 포인터B가 동일한 문자를 가리키므로 LSC는 3이 된다. 두 문자가 동일하므로 두 포인터를 이동시켜야 하지만 문자열B는 끝났으니 더 이상 비교할 문자가 없다. 여기서 알고리즘을 마무리한다.

 

 

문자열 A와 문자열 B의 최종 LCS는 3이 된다.

 

 

---

 

 

 

참고자료