LCS 알고리즘

1. LCS 알고리즘이란?

LCS(Longest Common Subsequence) 알고리즘은 단어 그대로 해석하자면

가장 긴 공통 부분 문자열이다. 

 

부분 문자열(Subsequence)이란 어떤 단어에서 연속되지 않는 부분 문자열을 뜻하는데

연속된 부분 문자열을 나타내는 부분 문자열(Substring) 도 있다.

(따라서 string 헤더파일의 substr()은 substring을 의미한다)

 

두 부분 문자열의 차이는 예를 들자면

 

• pringles
• sangeles

이렇게 두 문자열이 있을 때

가장 긴 Subsequence는

• pringles
• sangeles

"ngles" 가 되고

 

가장 긴 Substring은

 

• pringles
• sangeles

"les" 가 된다.

 

위에서 알 수 있듯 가장 긴 Substring은 반드시 가장 긴 Subsequence 보다 같거나 짧고,

Subsequence에 포함된다고 할 수 있다.

 

2. LCS 알고리즘 구현

그렇다면 LCS 알고리즘은 어떻게 구현할까?

정답부터 말하자면 2차원 DP(Dynamic Programming)으로 보통 구현한다. 예시를 보면서 천천히 이해해보자.

 

아래는 위 단어를 예시로 LCS를 찾는 과정이다.

 

	p	r	i	n	g	l	e	s
s	0	0	0	0	0	0	0	1

• 우선 두 단어 중 한 단어를 고정해둔다.
• 고정되지 않은 단어를 첫 글자부터 차례차례 고정된 단어와 비교를 하는데, 글자가 일치하면 그 전의 결과값에 +1 해주고, 일치하지 않다면 그 전 결과값 중 큰 값을 넣어준다.
• 마지막 숫자가 두 문자열의 LCS 길이가 된다.
• 여기서는 마지막 부분이 1이므로, pringles 와 s의 LCS는 1이 된다.

 

	p	r	i	n	g	l	e	s
s	0	0	0	0	0	0	0	1
a	0	0	0	0	0	0	0	1

 

• 어라? 여기서 a는 고정 문자열과 일치하는 부분이 하나도 없는데 끝에 1이 추가 되었다!
• 위에서 말한 "문자가 일치하지 않을 때 그 전 결괏값" 은 두 가지가 있는데, 하나는 같은 행의 바로 전(a,e) 값이고 다른 하나는 같은 열의 바로 전(a-1,s) 값이 된다. 따라서 왼쪽과 위쪽을 봐야하는데, 둘 중 큰 값은 1이므로 1을 넣어주게 된 것이다.

 

	p	r	i	n	g	l	e	s
s	0	0	0	0	0	0	0	1
a	0	0	0	0	0	0	0	1
n	0	0	0	1	1	1	1	1

 

다음은 이렇게

 

	p	r	i	n	g	l	e	s
s	0	0	0	0	0	0	0	1
a	0	0	0	0	0	0	0	1
n	0	0	0	1	1	1	1	1
g	0	0	0	1	2	2	2	2

 

• g가 ng와 겹치므로 2로 승격된다.
• ng는 길이가 2인 Subseqeunce

	p	r	i	n	g	l	e	s
s	0	0	0	0	0	0	0	1
a	0	0	0	0	0	0	0	1
n	0	0	0	1	1	1	1	1
g	0	0	0	1	2	2	2	2
e	0	0	0	1	2	2	3	3

 

• nge는 길이가 3인 Subsequence

 

	p	r	i	n	g	l	e	s
s	0	0	0	0	0	0	0	1
a	0	0	0	0	0	0	0	1
n	0	0	0	1	1	1	1	1
g	0	0	0	1	2	2	2	2
e	0	0	0	1	2	2	3	3
l	0	0	0	1	2	3	3	3

 

• 이때 길이가 3인 Subsequence는 "nge" 가 될 수도 있고 "ngl"이 될 수도 있다. 보통 LCS를 직접 출력하는 문제에서는 "ngl"을 출력값으로 내는데, 이유는 뒤에서 설명하도록 하겠다.

 

	p	r	i	n	g	l	e	s
s	0	0	0	0	0	0	0	1
a	0	0	0	0	0	0	0	1
n	0	0	0	1	1	1	1	1
g	0	0	0	1	2	2	2	2
e	0	0	0	1	2	2	3	3
l	0	0	0	1	2	3	3	3
e	0	0	0	1	2	3	4	4

 

• 길이가 4인 Subsequence "ngle"

 

	p	r	i	n	g	l	e	s
s	0	0	0	0	0	0	0	1
a	0	0	0	0	0	0	0	1
n	0	0	0	1	1	1	1	1
g	0	0	0	1	2	2	2	2
e	0	0	0	1	2	2	3	3
l	0	0	0	1	2	3	3	3
e	0	0	0	1	2	3	4	4
s	0	0	0	1	2	3	4	5

 

• 드디어 우리가 찾던 길이가 5인 Subsequence "ngles"를 만들어냈다!

아까 위에서 설명했듯, 숫자의 변동은 두 가지로 인해 이루어질 수 있다.

• 문자가 일치할 경우
• 문자가 불일치하나, 바로 위 또는 바로 왼쪽 값의 최댓값이 0이 아닌 경우

이를 dp로 표현한다면 각각의 상황은

• if(i == j) d[i][j] = d[i-1][j-1] + 1
• if(i != j) d[i][j] = max(d[i][j-1], d[i-1][j])

자 여기까지 왔으면 dp 구현은 간단하다.

 

 

• LCS 길이 찾기 코드

int na = a.size();
int nb = b.size();
for (int i = 1; i < na; i++) {
    for (int j = 1; j < nb; j++) {
        if (a[i] == b[j]) {
            d[i][j] = d[i - 1][j - 1] + 1;
        }
        else {
            d[i][j] = max(d[i - 1][j], d[i][j - 1]);
        }
    }
printf("%d\n", d[na - 1][nb - 1]);

위에서는 이해를 돕기위해 앞에 공백 문자를 집어넣지 않았으나,

실제로 코드로 구현할 때는 문자열 앞에 공백문자를 하나 추가하여 배열 index 초과를 막아야 합니다!

 

 

3. LCS 단어 찾기

LCS의 길이를 알고있고, 그 정보들을 d[i][j] 배열에 모두 저장했다면

우린 저장한 값들을 역추적해서 LCS 단어를 쉽게 찾을 수 있다.

 

먼저 우리가 저장해온 배열을 다시 꺼내어보자.

	p	r	i	n	g	l	e	s
s	0	0	0	0	0	0	0	1
a	0	0	0	0	0	0	0	1
n	0	0	0	1	1	1	1	1
g	0	0	0	1	2	2	2	2
e	0	0	0	1	2	2	3	3
l	0	0	0	1	2	3	3	3
e	0	0	0	1	2	3	4	4
s	0	0	0	1	2	3	4	5

 

여기서 우리가 주의깊게 봐야할 점은 이 배열들의 값이 언제 +1씩 추가 되었는가? 이다.

이 부분을 명확히 보려면, 왼쪽 대각선의 값이 1씩 차이나는 부분을 봐야하는데

 

예시로 만든 문자열의 LCS는 모두 붙어있어서 그렇지만.. LCS 문자를 실제로 찾을 때는

• (i,j) 부터 시작해서 (i-1,j-1), (i-1,j), (i, j-1)의 값이 모두 1 차이나면 -> 정답에 (i-1,j-1) 문자 추가하고 index 변경
• 차이나지 않으면 -> 일치하는 부분으로 옮기기 (column 우선)

를 통해 정답을 구하고, 그 정답 문자열을 뒤집어주면 완벽한 LCS 문자가 탄생한다!

 

 

• LCS 문자열 구하기 코드

    string ans;
    int i = na - 1;
    int j = nb - 1;
 
    while (d[i][j] != 0) {
        if (d[i][j] == d[i][j - 1]) { //앞의 값과 같다면
            j--;
        }
        else if (d[i][j] == d[i-1][j]) { //위의 값과 같다면 
            i--;
        }
        else { //대각선이 1차이
            ans += a[i];
            i--;
            j--;
        }
    }
    reverse(ans.begin(), ans.end());
    cout << ans << "\n";
 
 

 

 

4. LCS 관련 문제

 

• 백준 5582 공통 부분 문자열 : https://suhwanc.tistory.com/82
• 백준 9251 LCS : https://suhwanc.tistory.com/81