[Algorithm]최장 공통 부분 수열(LCS, Longest Common Sequence)

LCS

최장 공통 부분 수열 알고리즘은, 여러 문자열의 부분 수열 중 가장 긴 수열을 찾는 알고리즘이다.

여기서는 두 개의 수열에 대한 해만 다룰 것이다.

diff 프로그램의 근간이되는 알고리즘이다.

시간 복잡도

주어진 수열의 개수가 일정할 때 DP(Dynamic Programming), 동적 계획법으로 풀이할 수 있다.

길이가 N과 M인 두 수열이 주어졌을 때 일반적으로 O(N * M)의 시간복잡도를 가진다.

LCS 문제의 풀이

LCS는 *optimal substructure와 **overlapping subproblems 성격을 지니고 있다. 두 속성을 공유하는 경우 하위 부분 문제들에 대한 최적해를 저장한 메모이제이션 기법을 통한 DP풀이를 사용할 수 있다.

*optimal substructure: 하위 문제의 최적해로부터 전체의 최적해를 구성할 수 있는 경우를 말한다. 그리디 알고리즘이 대표적인 예.

**overlapping subproblems: 큰 문제를 작은 문제로 나누었을 때 같은 부분 문제가 여러 번 반복하여 나타나는 경우를 말한다.

https://en.wikipedia.org/wiki/Optimal_substructure

Optimal substructure - Wikipedia

https://en.wikipedia.org/wiki/Overlapping_subproblems

Overlapping subproblems - Wikipedia

 

접두사(prefix)

임의의 수열 S를 두고, 첫 문자열부터 n개의 문자를 포함하는 부분 문자열을 접두사(prefix), Sn이라 하자.

S가 AKKA일 때 S가 가능한 접두사는 아래와 같다.

S1 = A

S2 = AK

S3 = AKK

S4 = AKKA

여기서 두 수열의 X와 Y의 LCS는 두 속성에 의존한다.

첫 번째 속성

두 수열이 같은 원소로 끝나는 경우 동일한 원소를 제거함으로써 수열의 길이를 줄일 수 있다.

짧아진 수열의 LCS를 찾은 뒤 삭제한 원소를 붙여준다.

 

BANANA와 ATANA 두 수열을 보자.

1. 각 수열 끝의 공통된 요소를 제거한다. 여기서는 ANA를 삭제할 수 있다.

2. BAN과 AT 의 LCS를 구한다. 여기서는 A이다.

3. 삭제한 ANA를 결합하여 LCS "AANA"를 구할 수 있다.

LCS(X_n, Y_m) = LCS( X_n-1, Y_m-1) + xn

*xn: Xn과 Ym의 공통 요소이기 때문에 LCS 뒤에 붙는 경우를 나타낸다.

두 번째 속성

두 수열이 같은 원소로 끝나지 않는다면 LCS는 LCS(X_n, Y_m-1)와 LCS(X_n-1, Y_m) 중 더 긴 수열이다.

수열 X: ABCDEFG (n개의 원소)

수열 Y: BCDGK (m개의 원소)

두 수열의 LCS의 마지막 문자는 수열 X의 마지막 원소인 'G'로 끝나거나, 그렇지 않다.

1. LCS가 'G'로 끝나는 경우

LCS는 K로 끝날 수 없으므로 Y의 'K'를 제거하더라도 손실이 일어나지 않는다.

-> LCS(X_n, Y_m-1)

2. LCS가 'K'로 끝나는 경우

LCS는 G로 끝날 수 없으므로 X의 'G'를 제거하더라도 손실이 일어나지 않는다.

-> LCS(X_n-1, Y_m)

LCS 함수의 정의

 X = (x1, x2...xm), Y = (y1, y2...yn). X의 접두사는 X1, 2,...m이고, Y의 접두사는 Y1, 2,...n이다.

X[i]와 Y[j]의 요소가 같다면, LCS에 원소 X[i]를 더한다.

같지 않다면 LCS(X[i - 1], Y[j]) 와 LCS(X[i], Y[j - 1]) 중 더 긴 것을 가진다.

만약 index가 0이라면 비어있다는 필요조건을 추가한다.

LCS를 구하는 예시

수열 C: AGCAT

수열 R: GAC

LCS 함수는 0번째 원소를 이용하므로 0인 경우의 접두사를 정의하는 것이 편하다.

[초기값]

	\0	A	G	C	A	T
\0	\0	\0	\0	\0	\0	\0
G	\0
A	\0
C	\0

LCS(C1, R1): C1('A')과 R1('G')은 값이 다르므로 LCS(C1, R0)과 LCS(C0, R1) 중 더 긴 값을 찾는다. 두 값 모두 '/0'이므로 LCS(C1, R1)은 '/0'을 가진다.

LCS(C1, R2): C1('G')와 R2('G')는 값이 같으므로 LCS(C0, R1)의 뒤에 'G'가 붙는다. LCS(C0, R1)는 비어있으므로 LCS(C1, R2)는 "G"이다.

LCS(C1, R3): C1('G')와 R3('C')는 값이 다르므로 LCS(C2, R1)와 LCS(C1, R2) 중 더 긴 값을 찾는다. 각각 '\0'와 'G'이므로 LCS(C1, R2), 'G'를 택한다.

LCS(C2, R4), LCS(C2, R5)은 위와 같은 방법으로 "G"가 된다.

	\0	A	G	C	A	T
\0	\0	\0	\0	\0	\0	\0
G	\0	\0	G	G	G	G
A	\0
C	\0

LCS(C2, R1): C2('A'), R1('A')로 값이 같으므로 LCS(C1, R0)의 값에 'A'를 붙인다. LCS(C1, R0)의 값이 비어있으므로 "A"가 된다.

LCS(C2, R2): 각각 'A'와 'G' 이므로 LCS(C1, R2), LCS(C2, R1) 중 긴 값을 찾는다. 값 'A'와 'G' 모두 길이가 1이므로 둘 모두를 가질 수 있다.

LCS(C2, R3): 각각 'A'와 'C' 이므로 LCS(C2, R2), LCS(C1, R3) 중 긴 값을 찾는다. 값은 각각 "A" & "G" 와 "G" 이다. LCS(C2, R2)가 'G'를 포함하고 있으므로 'A'와 'G' 모두를 가질 수 있다.

LCS(C2, R4): 각각 'A'와 'A로 값이 같으므로 LCS(C1, R3) 'G'의 값에 'A'를 붙인다. 따라서 "GA"가 된다.

LCS(C2, R5): 각각 'A'와 'T' 이므로 LCS(C2, R4), LCS(C1, R5) 중 긴 값을 찾는다. 값은 각각 "GA"와 "G" 이다. LCS(C2, R2)의 값이 "GA"로 더 크므로 GA를 택한다.

	\0	A	G	C	A	T
\0	\0	\0	\0	\0	\0	\0
G	\0	\0	G	G	G	G
A	\0	A	A & G	A & G	GA	GA
C	\0

LCS(C3, R1): 각각 'C'와 'A'이므로 LCS(C2, R1)와 LCS(C2, R0) 중 더 큰 값 'A'를 택한다.

LCS(C3, R2): 각각 'C'와 'G'이므로 LCS(C2, R2)와 LCS(C3, R2)을 비교한다. 길이가 같기 때문에 A, G 두 값 모두 가질 수 있다.

LCS(C3, R3): 각각 'C'와 'C'이므로 LCS(C2, R2)의 값에 'C'를 붙일 수 있다. 이전의 값이 A와 G를 모두 가질 수 있었으므로 AC, GC 모두 가질 수 있다.

LCS(C3, R4): 각각 'C'와 'A'이므로 LCS(C2, R4)와 LCS(C3, R3)의 값 중 큰 값을 택한다. 두 값 모두 길이가 2인 LCS를 가질 수 있으므로 여기서는 AC, GC, GA 모두를 가질 수 있다.

LCS(C3, R5): 위와 같다.

	\0	A	G	C	A	T
\0	\0	\0	\0	\0	\0	\0
G	\0	\0	G	G	G	G
A	\0	A	A & G	A & G	GA	GA
C	\0	A	A & G	AC & GC	AC & GC & GA	AC & GC & GA

출처: wikipedia.org

최장 공통 부분 수열 - 위키백과, 우리 모두의 백과사전

 

LCS를 활용하는 문제

BOJ 9251 LCS: https://www.acmicpc.net/problem/9251

풀이 과정은 곧 업로드 하도록 하겠습니다. 

 

 

※ 질문, 개선점, 오류가 있다면 댓글로 남겨주세요 :)