LCS 최장 공통 부분 수열 알고리즘

LCS(Longest Common Subsequence) 알고리즘은 두 문자열의 최장 공통부분 문자열을 구하는 알고리즘이다.

문자열 ABCD와 문자열 BCDE가 있으면 이 두 문자열 사이에서 공통으로 갖는 부분 수열인 BCD를 찾는 것이다.

 

LCS 함수 식, 출처 : 위키백과

LCS의 함수 식은 두 문자열을 한 글자씩 비교하면서 같은 글자일 때 이전 글자 비교에서 찾은 부분 문자열 길이에 +1을 하고, 그러지 않을 경우에는 바로 이전 문자열 길이와, 이전 글자가 현재와 같은 글자에서의 최장 부분 문자열 길이 중 최댓값을 선택하는 것이다. 시간 복잡도는 비교하는 각 문자열의 크기 M과 N만큼 비교를 하기 때문에 O(MN)의 시간 복잡도를 갖는다. 그렇다면 예시로 두 문자열의 LCS를 구해보도록 하자

 

문자열 ACAYKP과 문자열 CAPCAK의 최장 공통부분 문자열을 구해보도록 해보자

		A	C	A	Y	K	P
	0	0	0	0	0	0	0
C	0
A	0
P	0
C	0
A	0
K	0

ACAYKP를 STR1 문자열이라고 하고 CAPCAK를 STR2 문자열이라고 하자

먼저 STR1[1]과 STR2 [1]를 비교했을 때 'A'와 'C'는 같지 않으니 LCS 함수 식에 의해 TABLE [1][0] TABLE [0][1] 중에서 최댓값을 가지는 값인 0이 TABLE [1][1]의 값이다.

그다음 문자인 STR1[2]와 STR2 [1]를 비교했을 때 'C'와 'C'는 같은 문자이다. 그러므로 TABLE [0][1]에 1을 더한 값인 1이 TABLE [1][2]의 값으로 한다. 이 이후에도 이와 같은 방법으로 TABLE을 채워 넣는다.

 

		A	C	A	Y	K	P
	0	0	0	0	0	0	0
C	0	0	1	1	1	1	1
A	0
P	0
C	0
A	0
K	0

문자 C의 행을 채웠으니 다음 STR2[2]의 문자를 비교해보도록 하자

STR1 [1]과 STR2 [2]의 문자는 'A'와 'A'로 같은 글자이기 때문에 TABLE [1][0]의 값에서 1을 더한 값인 1이 TABLE [2][1]의 값이 된다. 그다음 글자인 STR1 [2]와 STR2 [2]는 'C'와 'A'로 같지 않다. 그러면 TABLE [2][1]과 TABLE [1][2] 중에서 최댓값을 가지는 값인 1이 TABLE [2][2]가 된다. STR1 [3]과 STR2 [2]는 'A'과 'A'로 같은 글자가 된다. TABLE [1][2]의 값에서 1을 더한 값인 2가 TABLE [2][3]의 값이 된다. 나머지 표를 같은 방식으로 끝까지 채워보자

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

 

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

최종적으로는 마지막 표와 같은 결과가 나올 것이다. 여기서 최장 공통 부분 수열의 길이는 최댓값인 4가 된다.

최장 부분 수열은 길이가 대각 방향에서 변한 지점을 하나씩 고르면 그것이 최장 부분수열이 된다.

위의 표를 참고해서 부분수열을 추출하자면 다음과 같다

 

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

색깔로 표시한 부분이 대각 방향에서 값을 얻어온 문자이다.

모든 대각선 값을 가져오는 것이 아닌 최대값을 얻은 맨 마지막 행부터 시작하여 계단식으로 앞글자로 오면서 생기는 대각선의 값이 부분 문자열이다.

최장 공통 부분 수열은 ACAK라는 것을 알 수가 있다.

 

동적 계획법으로 해결하는 알고리즘으로 DP를 공부한다면 알아두도록 하자

직접 코딩을 해보고 싶다면 백준 사이트의 LCS 문제를 추천한다.

 

백준 9251번: LCS

9251번: LCS