Longest Common Subsequence/Substring (LCS) Algorithm

Dynamic Programming 카테고리의 알고리즘입니다.

 

두 개의 문자열이 있다고 가정합시다. 각각 subject, target이라고 부르겠습니다.

subject = ACAYKP, target = CAPCAK이라고 합니다.

 

이 때, subject = ACAYKP의 부분 수열이라 함은 다음을 가리킵니다.

0, A, CAY, CYP, ACAYKP... 등등.

가장 작은 부분 수열은 공집합이며, 가장 큰 부분 수열은 문자열 그 자신입니다.

 

여기서 중요하게 짚고 넘어가야 할 점이 있습니다.

LCS라는 표현을 쓸 때, longest common SUBSEQUENCE인지, longest common SUBSTRING인지 잘 확인해야 합니다.

번역하면 최장 공통 수열, 최장 공통 문자열이 되겠습니다.

이 둘의 결정적인 차이점은, 연속되어 있느냐 연속되어 있지 않느냐 입니다.

substring은 연속되어 있지 않는 경우를 포함합니다. 위에서 든 예시 중 CYP가 이 경우에 해당합니다.

subsequence는 오직 연속된 경우만을 포함합니다. 위에서 든 예시 중 CYP는 이 경우에 포함되지 않을 것입니다.

 

이 문제가 dynamic programming 카테고리에 들어가는 이유는 무엇일까요?

두 문자열 subject, target을 비교한다고 해 봅시다: ACAYKP, CAPCAK.

계산의 수월함을 보이기 위해, 먼저 LCS의 길이 LCS_length를 나타내 봅니다.

 

당연한 수순은 맨 앞에서부터 비교해 보는 것입니다.

• A와 CAPCAK은 모두 A라는 LCS를 공유합니다. 따라서 이 시점에서의 LCS_length = 1입니다.
• AC와 CAPCAK는 모두 AC라는 LCS를 공유합니다. 따라서 이 시점에서의 LCS_length = 2입니다.
• ACA와 CAPCAK는 모두 ACA라는 LCS를 공유합니다. 따라서 이 시점에서의 LCS_length = 3입니다.
• ACAY와 CAPCAK는 여전히 ACA라는 LCS를 공유합니다. 따라서 이 시점에서의 LCS_length = 3입니다.
• ACAYK와 CAPCAK는 모두 ACAK라는 LCS를 공유합니다. 따라서 이 시점에서의 LCS_length = 4입니다.
• ACAYKP와 CAPCAK는 모두 ACAK라는 LCS를 공유합니다. 따라서 이 시점에서의 LCS_length = 4입니다.

위 과정을 보면, 문자열에서 글자 하나가 추가되어 비교할 때마다, 조건이 맞으면 LCS_length의 값이 증가하는 것을 볼 수 있습니다.

그렇다면 매번 길이를 전부 확인할 필요 없이, 이전의 LCS_length의 값을 꺼내어 거기에 1을 더하는 방식으로 접근하면 되지 않을까요?

이것이 LCS algorithm의 dynamic programming식 접근법입니다.

	0	C	A	P	C	A	K
0	0	0	0	0	0	0	0
A	0	0	1	1	1	1	1
C	0	1	1	1	2	2	2
A	0	1	2	2	2	3	3
Y	0	1	2	2	2	3	3
K	0	1	2	2	2	3	4
P	0	1	2	3	3	3	4

각 문자열에서 검사를 하여 LCS_length의 길이를 나타낸 표입니다.

위 표를 볼 때 주목할 점은 현재 위치 (i,j)와, 이전 좌표 3개 (i-1, j), (i, j-1), (i-1, j-1)입니다.

subject[i]와 target[j]를 비교해 보며, 이 둘이 같은 경우에는, 이전 좌표 3개의 값이 같으며, 좌표 (i, j)는 이보다 하나 증가된 값을 가집니다.

이 둘이 다른 경우에는, 예를 들어 CAP, ACAYK를 비교할 때를 봅시다. 이때의 값은 2이며, 이전 좌표 3개의 값도 모두 2입니다.

또, CAPCA와 ACAYKK를 봅시다. 이때의 값은 3이며, 이전 좌표 3개의 값은 각각 2, 3, 2입니다.

 

정리하면 아래와 같습니다.

• 두 문자 subject[i]와 target[j]이 같으면, 현재 좌표의 값에 이전 좌표의 값 + 1을 더한다.
• 두 문자 subject[i]와 target[j]이 다르면, 현재 좌표의 값을 이전 좌표 3개의 값 중 최댓값으로 한다.
• 최종적으로, 우측 하단의 숫자가 LCS_length가 된다.

이제 LCS_length를 구했습니다. 이를 이용하여 어떻게 LCS를 구할 수 있을까요?

두 가지에 주목해 봅시다.

• subject[i]와 target[j]가 같을 때, 현재 좌표의 값이 이전 좌표의 값들보다 1 증가하였다.
• 표에서 subject[i]와 target[j]가 같아 값이 증가되는 일은 한 번 이상 발생한다.

이를 다른 말로 옮기면 다음과 같습니다.

• 현재 좌표의 값이 이전 좌표의 값들보다 1 크다면, 문자열이 같았음을 나타냅니다. 이를 출력할 string에 포함합니다.
• 값이 증가되는 일을 한 번만 세어야 합니다. 즉 loop를 이용하고 있다면, 예를 들어 1->2가 되는 경우가 발생하면, 이를 출력할 string에 포함한 후, 1->2를 또 세는 경우가 발생하지 않도록 loop를 break 합니다.

그 다음으로 고려할 문제는, 단어를 확인하는 순서입니다.

위 문자열을 가로 순서대로 비교할 때, 세로 순서대로 비교할 때를 각각 봅시다.

 

가로 순서대로 비교하는 경우, LCS = ACAK가 됩니다.

세로 순서대로 비교하는 경우, LCS = CAPK가 됩니다.

 

이게 무슨 의미일까요? 세로 순서대로 비교할 때, 처음 LCS_length가 3이 되는 때와 4가 되는 때를 비교해 봅시다.

세로 좌표값 j를 보면, LCS_length가 3일 때의 좌표값 j는 6이며, 4일 때의 좌표값 j는 5입니다.

이런 경우는 잘못된 탐색이라고 할 수 있습니다.

따라서 탐색할 때 몇 가지 규칙을 두어야 합니다.

• 뒤에서부터 탐색한다.
• 한번 탐색이 완료된 행, 열은 탐색 대상에서 제외한다. 탐색이 완료된 좌표보다 작은 값에서부터 탐색을 이어간다.
• 이전 좌표 3개의 값이 전부 현재 탐색한 좌표의 값보다 작아야 한다.

위의 규칙에 따라 탐색을 하면, KACA라는 결과를 얻습니다.

이의 순서를 뒤집으면 ACAK, 즉 원하는 결과가 나옵니다.

 

LCS가 사용되는 백준 문제들은 다음을 참고하세요:

• 백준 9251. LCS
• 백준 9252. LCS 2
• 백준 5582. 공통 부분 문자열
• 백준 15483. 최소 편집
• 백준 1958. LCS 3