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

LCS알고리즘

오늘은 LCS 알고리즘에 대해서 알아보도록 하겠다. LCS(Longest Common Subsequence, 최장 공통 부분 수열)이다.

substring과 subsequence의 차이점은 예를 들어서 'carrot'이라는 단어를 자를때, 

Substring : 연속해서 이어져 있는 것이다. (예시) carr 또는 rot 등등.

Subsequence : 순서는 바뀌지 않지만, 띄어져서도 이어지는 녀석을 칭한다. (예시) cro 또는 arrt 등등. 

---

LCS는 두 수열이 주어졌을 때, 공통으로 들어있는 부분 수열 중 가장 긴 것을 찾는 것이다.

orange와 neopong 이 주어졌을 때 공통으로 있는 부분 수열은 'ong'가 될 것이다..

접근

수열 A인 abcdef와 수열 B인 bce가 있다. A의 맨 마지막 단어를 지워보자. abcde가 될 것 이다. 그렇지만 A와 B의 LCS의 길이는 계속 같다. 한 번 더 A의 맨 마지막을 지워보자. abcd가 될 것이고 LCS의 길이는 하나가 줄게 된다. 

이렇듯이 수열의 맨 뒤를 제거하게 되면 ①LCS의 길이가 줄거나 ②그대로인 경우로 나눠진다.

참고로, LCS 알고리즘에서는 수열 A와 B 둘 중 하나를 기준으로 잡고 비교해야 한다.

경우

1) 두 수열의 마지막이 모두 LCS에 속할 경우

A[i] == B[j](A와 B의 문자가 같다)일때, 

A와 B의 LCS는 A에서 마지막 한 개 뺀 것과 B에서 마지막 한 개 뺀 것 간의 LCS + 1와 같다.

즉, 일반화를 하면 LCS[i][j] = LCS[i - 1][j - 1] + 1이다. 

예시) 'axpe'와 'aowpe'의 LCS는 'axp'와 'aowp'의 LCS + 1과 같다.

2) A 수열의 마지막이 LCS에 속하지 않을 경우

A[i] != B[j](A와 B의 문자가 다르다)일때,

A와 B의 LCS는 A에서 마지막 한 개 뺀 것과 B의 LCS와 같다.

즉, 일반화를 하면 LCS[i][j] = LCS[i - 1][j]이다.

예시) 'abdop'와 'ebd'의 LCS는 'abdo'와 'ebd'의 LCS와 같다.

3) B 수열의 마지막이 LCS에 속하지 않을 경우

A[i] != B[j](A와 B의 문자가 다르다)일때,

A와 B의 LCS는 B에서 마지막 한 개 뺀 것과 A의 LCS와 같다.

즉, 일반화를 하면 LCS[i][j] = LCS[i][j - 1]이다.

예시) 'abc'와 'axbe'의 LCS는 'abc'와 'axb'의 LCS와 같다.

A[i] != B[j]인 경우는 경우 2와 3이 충족한다. 그렇지만 우리는 최장 공통 부분 수열을 구해야 하기 때문에 

둘 중에 큰 값이 나온 것을 고르면 된다. -> if(A[i] != B[j]), LCS[i][j] = max(LCS[i - 1][j], LCS[i][j - 1]

행렬을 이용한 보여주기!

되게 신기하지만 이 친구는 다이나믹 프로그래밍을 통해 문제를 해결할 수 있다. 우선 행렬을 통해 어떻게 구현되는지 알아보자.

백준 문제에서도 나온 문자열 두 개를 통해 알아보자. 'ACAYKP'와 'CAPCAK'가 있다.

먼저 아래와 같이 세팅해준다.

LCS[][0] 와 LCS[0][]을 모두 0으로 초기화 해주면 된다. 저 ø은 그냥 인덱스를 1부터 시작하기 위해서라고 생각하면 될 것 같다..

우리가 아까전에 세 가지 경우에서 봤던 것 처럼 똑같이 해주면 된다.

C부터 시작해서 상단에 있는 기준이 되는 단어들과 매칭을 한다. C와 A는 다르니깐 위쪽 또는 왼쪽 중 큰 수를 가져간다. 그래서 LCS[A][C]는 0이 된다. 

이제 C와 C를 비교한다. 둘이 같으므로 LCS[i - 1][j - 1] + 1을 해주는데 행렬상으로는 좌측 상단이므로 0 + 1을 해주면 된다.

이렇게 계속 반복을 해주면

이렇게 행렬이 채워진다. 

고로 'ACAYKP'와 'CAPCAK'의 LCS의 길이는 4가 되는 것이다.(항상 LCS의 최대 길이는 행렬 맨 끝에 위치한다)

아래 코드를 참고하길 바란다.

#include <cstdio>
#include <cstring>
#include <algorithm>
char str1[1010];
char str2[1010];
int LCS[1010][1010];
int main()
{
    scanf("%s", &str1);
    scanf("%s", &str2);
    int s1 = strlen(str1);
    int s2 = strlen(str2);
 
    for (int i = 1; i <= s1; i++) {
        for (int j = 1; j <= s2; j++) {
            if (str1[i - 1] == str2[j - 1])
                LCS[i][j] = LCS[i - 1][j - 1] + 1;
            else
                LCS[i][j] = std::max(LCS[i - 1][j], LCS[i][j - 1]);
        }
    }
    printf("%d\n", LCS[s1][s2]);
    
    return 0;
}