최장 공통 부분수열 (LCS)

LCS( Longest Common Subsequence)

LCS란 가장 긴 공통의 부분집합을 말한다.

 

예를 들어 

x = "ECADADABRBCRDARA"

Y = "ABRACADABRA"라는 변수가 있다면 x와 y의 LCS는 다음과 같다.

 

부분 수열이기 때문에 문자 사이를 건너뛰어 공통되면서 가장 긴 부분 문자열을 찾으면 된다.

 

어떤 문자열 X와 Y가 있다고 할 때

Xn = X1X2 . . . Xn(길이를 n으로 갖는 문자열 Xn)

Ym = Y1Y2 ... Ym(길이를 m으로 갖는 문자열 Ym) 이라고 하면 

 

우리가 구하고자 하는 것은 X와 Y의 LCS이므로 

 

LCS(Xn,Ym) := (X[0..n]와 Y[0..m]를 사용하여 만들 수 있는 LCS의 길이)의 점화식을 세우면 된다.

 

LCS(n,m)의 경우를 두 가지로 나눌 수 있는데

 

1. 만약 Xn == Ym인 경우

2. Xn != Ym인 경우

 

1번의 경우 같은 문자열이 발생했으므로 공통 부분집합이 길이가 +1이 된다.

 

따라서

LCS(n,m) = LCS(Xn-1,Ym-1) + 1 으로 나타낼 수 있다.

 

2 번의 경우 서로 다르지만 결과론적으로 Xn, Ym이 포함이 될지 안될지 모르는 상황이다.

 

다시 말해

 

1. X의 n번째 원소가 Y의 m을 제외한 1부터 m-1까지의 스트링 값에 포함이 안된다는 보장이 없고,

2. 반대로 Y도 m 번째 원소가 X의 1 ~ n-1까지의 스트링 값에 포함이 안된다는 보장이 없다.

 

따라서 두 가지 경우를 고려해야 하므로  

LCS(n,m) = max( LCS(n, m-1) , LCS(n-1, m)) 으로 나타낼 수 있다. 

 

위 점화식을 코드로 작성할 때 LCS 테이블을 통해 확인할 수 있다.

 

X = "BDCAB"

Y = "ABCBD" 의 테이블을 만들어보면 다음과 같다.

	-	A	B	C	B	D
-	0	0	0	0	0	0
B	0
D	0		1번	2번
C	0		2번	LCS(3,3)
A	0
B	0

• 위에서 말한 1,2번의 경우 왼쪽, 왼쪽대각선, 위 방향을 확인해야 하는데 예외처리를 해주어야 하므로 처음에 '-'처리를 하여 글자가 없음을 나타내 곂치는 것이 없어 0을 표기해준다. 
• LCS(n,m)은 n행 m열 값을 말한다.

 

LCS(3,3)의 값을 알기 위해서는 (서로 C이므로 같은 상황. 즉, 1번의 경우임) 표에 1번이라고 적어놓은 곳의 값을 알아야 하고 그 값에 + 1을 한 값이 LCS(3,3)의 값이다.

 

만약 다르다면 표에 2번이라고 표시한 것 LCS(2,3)와 LCS(3,2)의 값 중 최대값을 취하면 된다.

 

모든 경우의 값을 이와 같은 방식으로 값을 구하면

	-	A	B	C	B	D
-	0	0	0	0	0	0
B	0	0	1	1	1	1
D	0	0	1	1	1	2
C	0	0	1	2	2	2
A	0	1	1	2	2	2
B	0	1	1	2	3	3

 

결국 LCS("BCB") 값 3을 구할 수 있게 된다.

 

 

시간복잡도

테이블 칸의 개수 * 칸을 채우는데 소요되는 시간(대각선 칸의 값을 확인 or 왼쪽, 위쪽 값 중 최대값을 확인)

= (n*m) * O(1)

=O(nm) 최악의 경우 O(n**2) 

 

 

 

참고

신찬수, 한국외대, 컴퓨터전자시스템공학부, 알고리즘 2020-1