Suhwanc

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 길이 찾기 코드
1
2
3
4
5
6
7
8
9
10
11
12
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]);
cs

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

실제로 코드로 구현할 때는 문자열 앞에 공백문자를 하나 추가하여 배열 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 문자열 구하기 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
    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";
 
 
cs
 

 

4. LCS 관련 문제

 

'algorithm class' 카테고리의 다른 글

[자료구조] 트라이(Trie)  (0) 2020.05.06
[C++] emplace 함수  (2) 2020.03.05
위상 정렬  (0) 2020.02.12
유니온 파인드(Disjoint-set) 이란?  (0) 2020.01.06
이진 탐색 트리  (0) 2019.10.21