알고리즘 #8_ 최장 공통 부분 수열(LCS: Longest Common Subsequence)

안녕하세요.

이번 포스팅에서는 최장 공통 부분 수열(LCS: Longest Common Subsequence)에 대해서 알아보도록 하겠습니다.

궁금하신 점이나 내용에 대한 피드백은 댓글을 이용해주세요 :)

---

1. 최장 공통 부분 수열

(LCS: Longest Common Subsequence)

먼저 최장 공통 부분 수열이 어떠한 것인지 알아보도록 하겠습니다.

문제를 이해하기 위해 다음을 가정합니다.

X = <AABCDDADABBCDCC>

Y = <ADABCCDCC>

이러한 두 수열 X, Y가 있습니다. 이때, <ABD>는 X와 Y의 공통 부분 수열입니다.

X = <AABCDDADABBCDCC>

Y = <ADABCCDCC>

위에서 X 수열과 Y 수열에 밑줄을 쳐놓은 부분을 통해 <ABD>는 X와 Y의 공통 부분 수열이라는 것을 알 수 있습니다.

꼭 연결되어 있어야 하는 것이 아니며, 단지 단조 증가하는 수열로써 존재하면 되는 것이죠.

그렇다면 최장 공통 부분 수열이란 무엇일까요?

바로 위에서 알아본 <ABD>와 같은 공통 부분 수열들 중에서, 가장 길이가 긴 것을 말합니다.

X, Y수열을 살펴보면 <ABD>를 제외하고도 <ABCD>와 같은 공통 부분 수열도 있습니다.

물론 하나의 공통부분 수열만 존재할 수도 있지만 2개 이상의 공통 부분 수열을 가질 수도 있습니다.

그러한 공통 부분 수열들 중에서 가장 길이가 긴 것을 우리는 최장 공통 부분 수열(LCS)라고 말합니다.

위의 X, Y수열에서는 아래 밑줄 친 것과 같이 <ADABCDCC> 가 가장 긴 공통 부분 수열, 최장 공통 부분 수열 입니다.

X = <AABCDDADABBCDCC>

Y = <ADABCCDCC>

2. 최장 공통 부분 수열의 최적 구조

우리는 앞에서 동적 프로그래밍의 최적 구조를 살펴보았습니다.

그럼 지금 알아보고 있는 LCS의 최적 구조는 어떻게 될까요? 바로 다음과 같습니다.

3. 최장 공통 부분 수열의 길이 구하기

그럼 이제 본격적으로, 최장 공통 부분 수열의 문제를 풀어보도록 합니다.

우리가 최종적으로 구해낼 것은 두 수열 X, Y가 있을 때 두 수열의 최장 공통 부분 수열의 길이입니다.

먼저 X의 i번째 문자열과 Y의 j번째 문자열까지의 최장 공통 부분 수열의 길이를 c[i,j]라고 가정합니다.

위의 내용을 하나씩 확인해보도록 하겠습니다.

3-1. i=0 or j=0

두 수열 중 하나의 수열의 길이가 0 이라면, 최장 공통 부분 수열의 길이도 0입니다. 서로 일치하는 문자가 전혀 존재할 수 없기 때문이죠.

3-2. i,j>0 and Xi = Yi

i,j가 양수인 것은 당연합니다. 문자열을 거꾸로 확인하지는 않을테니까요.

양수인 i,j에 대해서 Xi와 Yj가 서로 일치한다면 해당 문자는 최장 공통 부분 수열에 포함되는 문자일 것 입니다.

따라서 해당 문자를 제외한 나머지 문자열에서 LCS를 탐색하게 되고, 최종적으로 반환이 될때는 제외한 문자가 최장 공통 부분 수열에 포함되므로 +1을 합니다.

3-3. i,j>0 and Xi != Yi

양수인 i,j에 대해서 Xi와 Yj가 서로 일치하지 않다면, 각각의 수열에서 하나씩 제거해서 LCS를 탐색합니다.

Xi와 Yj가 서로 일치하지 않을 때는 각각의 수열에서 마지막 문자를 제거한, c[i,j-1] 또는 c[i-1,j] 둘 중 하나가 최장 공통 부분 수열을 포함하고 있을 것입니다. 

4. 테이블 그리기

그럼 위에서 알아본 방법으로 LCS를 어떻게 구할까요?

바로 아래와 같은 테이블을 통해서 LCS를 구합니다.

	j	0	1	2	3	4	5	6
i		Yi	B	D	C	A	B	A
0	Xi	0	0	0	0	0	0	0
1	A	0
2	B	0
3	C	0
4	B	0
5	D	0
6	A	0
7	B	0

먼저 X수열은 <ABCBDAB>이며 Y수열은 <BDCABA>라고 가정합니다.

테이블의 첫번째 열과 첫번째 행은 i또는 j가 0이므로 모두 0으로 채우도록합니다.

그리고 하나의 칸씩 채워보도록 하는데 이후 LCS의 길이뿐 아니라 그 수열까지 함께 구할 수 있도록 화살표를 함께 사용합니다.

각각에 대해서 탐색을 할때는 다음과 같은 방법을 이용합니다.

ㄱ) 두 문자가 같을 때, 좌측위에 있는 숫자에 1을 더한 값을 가지며 화살표는 좌측위를 가리킵니다.

ㄴ) 두 문자가 다를 때, 좌측이나 위에 있는 숫자중 큰 값을 가리키며 같은 값을 가집니다. 동일한 값일 때는 위의 값에 대해 행동합니다.

먼저, i가 1일때 1부터 6까지의 j에 대해 확인합니다.

X1는 A이며 Y1은 B이기 때문에 두 문자가 서로 다르고, 좌측과 위에 있는 숫자가 같은 값을 가지기에 그 값을 가지며 위를 가리킵니다.

X1과 Y2도 같은 방식이고, X1과 Y3 또한 같은 방식입니다.

X1과 Y4를 보시면 서로 같은 문자, A를 가지고 있습니다. 따라서 대각(좌측상단) 방향의 값보다 1큰 값인 1을 값으로 가지며 대각을 화살표로 가리킵니다.

이러한 방법으로 모든 칸을 채우면 아래와 같이 채워지게 됩니다.

따라서 LCS의 길이는 4이며 LCS수열을 구하고 싶다면 제일 좌측 하단에서부터 시작해 화살표 방향으로 따라가며 대각선방향을 가리키는 부분의 문자를 나열하면 됩니다.

---

이렇게 해서 최장 공통 부분 수열(LCS: Longest Common Subsequence)에 대해서 알아보았습니다.

추후 시간이 된다면 LCS알고리즘을 파이썬으로 직접 구현하여 테스트 해보도록 하겠습니다.