가장 긴 공통 부분 수열 (LCS - Longest Common Subsequence) 알고리즘

 LCS의 정의

• 가장 긴 공통 부분 문자열 (Longest Common Substring)

두 문자열의 가장 긴 부분 문자열이다.

문자열이란 끊어지지 않는 문자들의 연속이다.












• 가장 긴 공통 부분 수열 (Longest Common Sequence)

두 문자열의 가장 긴 부분 수열이다.

부분 수열이란 원래 수열에서 임의의 원소를 0개 이상 지워서 만든 수열이다.












이 포스팅에서는 가장 긴 공통 부분 수열을 다루며,


다루어지는 주제는 다음과 같다.

• N^2 풀이
• 경로 추적
• N*logN 풀이 - Using LIS
• 문자열이 N개일 때
• 메모리 최적화 

 N^2 풀이

동적 계획법을 사용하여 문제를 풀어보자.

작은 문제부터 시작하여 큰 문제를 해결하는 것 이다!

int solve (int i,  int j)  // A[0...i]와  B[0...j]에서, 최대 부분 수열의 길이

위와 같이 정의하면, 다음과 같은 점화식이 유도되며,

LCS(i,  j)의 값을 Cache[i][j]에 캐싱하면 반복문으로도 해결할 수 있다.

재귀를 추적하면 A[0],  B[0]에서 시작해서.

매 단계마다 A 또는 B를 한칸씩 증가시키면서,

모든 A[i],  B[j]의 쌍에 대해 위의 루틴을 실행한다.

A[i]와 B[j]가 동일한 경우에는,

부분 수열의 길이가 1 늘어난 것이고,

A[i],  B[j]가 동일하지 않은 경우에는,

지금까지의 부분 수열의 최대 길이를 반환해야 한다.

TOP-DOWN

#include <bits/stdc++.h>
using namespace std;
const int SIZE = 100;
int cache[SIZE+1][SIZE+1];
char A[SIZE+1];
char B[SIZE+1];

int LCS(int i, int j){
        //! base condition.
        if(i==0 || j==0) return 0;

        //! memoization.
        if(cache[i][j] != -1) return cache[i][j];

        //! solving.
        if(A[i] == B[j]) cache[i][j] = LCS(i-1, j-1) + 1;
        else cache[i][j] = max(LCS(i-1, j), LCS(i, j-1));
        return cache[i][j];
}


int main()
{
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        memset(cache, -1, sizeof cache);
        cin >> (A+1);
        cin >> (B+1);
        cout << LCS(strlen(A+1), strlen(B+1));
}

BOTTOM-UP

#include <bits/stdc++.h>
using namespace std;
const int SIZE = 100;
int cache[SIZE+1][SIZE+1];
char A[SIZE+1];
char B[SIZE+1];

int main()
{
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        
        memset(cache, 0, sizeof cache);
        cin >> (A+1);
        cin >> (B+1);

        for(int i=1; i<=strlen(A+1); i++){
                for(int j=1; j<=strlen(B+1); j++){
                        if(A[i]==B[j]) cache[i][j] = cache[i-1][j-1]+1;
                        else cache[i][j] = max(cache[i-1][j], cache[i][j-1]);
                }
        }
        cout << cache[strlen(A+1)][strlen(B+1)];
}

 경로 추적

다음은 cache[i][j]를 시각화 한 것 이다.

cache[i][j]가 갱신되는 케이스는 아래와 같다.

• if A[ i ]==B[ j ] )   LCS(i, j) = LCS(i-1,  j-1) + 1
• if A[ i ] !=B[ j ] )   LCS(i, j) = max(LCS(i-1, j),  LCS(i, j-1))

좌측 또는 상단에 자신과 같은 값이 있다면,

A[i]와 B[j]는 매칭되지 않아, 이전 최댓 값을 유지하려고 하는 경우이므로.

좌측 또는 상단의 최댓값 방향으로 이동하면 된다.

만약 그렇지 않다면, A[i]와 B[j]가 매칭되어 +1된 경우이므로. 

해당 문자를 스택에 삽입하고, 왼쪽 위 대각선 방향으로 이동하면 된다.

문자열이 N개 일 때 LCS

2개인 경우에서 재귀를 추적했을 때.

A[0],  B[0]에서 시작하여, 하나를 선택해서 증가시키고 LCS를 계산했다.

일반화 하면  N개의 단어 중, 하나를 선택해서 증가시키고 LCS를 계산하면 된다.

TOP-DOWN

#include <bits/stdc++.h>
using namespace std;

const int SIZE = 100;
int cache[SIZE+1][SIZE+1][SIZE+1];
char A[SIZE+1];
char B[SIZE+1];
char C[SIZE+1];

int LCS(int i, int j, int k){
        //! case condition.
        if(i==0 || j==0 || k==0) return 0;

        //! memoization.
        if(cache[i][j][k] != -1) return cache[i][j][k];

        //! solving.
        if(A[i]==B[j] && B[j]==C[k]) {
                cache[i][j][k] = LCS(i-1, j-1, k-1)+1;
        }
        else {
                int val = 0;
                val = max(val, LCS(i-1, j, k));
                val = max(val, LCS(i, j-1, k));
                val = max(val, LCS(i, j, k-1));
                cache[i][j][k] = val;
        }
        return cache[i][j][k];
}

int main()
{
        cin.tie(nullptr);
        ios::sync_with_stdio(false);

        memset(cache, -1, sizeof cache);
        cin >> (A+1);
        cin >> (B+1);
        cin >> (C+1);

        cout << LCS(strlen(A+1), strlen(B+1), strlen(C+1));
}

BOTTOM-UP

#include <bits/stdc++.h>
using namespace std;

const int SIZE = 100;
int cache[SIZE+1][SIZE+1][SIZE+1];
char A[SIZE+1];
char B[SIZE+1];
char C[SIZE+1];

int main()
{
        cin.tie(nullptr);
        ios::sync_with_stdio(false);

        memset(cache, 0, sizeof cache);
        cin >> (A+1);
        cin >> (B+1);
        cin >> (C+1);

        for(int i=1; i<=strlen(A+1); i++){
                for(int j=1; j<=strlen(B+1); j++){
                        for(int k=1; k<=strlen(C+1); k++){
                                if(A[i]==B[j] && B[j]==C[k]) {
                                        cache[i][j][k] = cache[i-1][j-1][k-1]+1;
                                }
                                else {
                                        int val = 0;
                                        val = max(val, cache[i-1][j][k]);
                                        val = max(val, cache[i][j-1][k]);
                                        val = max(val, cache[i][j][k-1]);
                                        cache[i][j][k] = val;
                                }
                        }
                }
        }
        cout << cache[strlen(A+1)][strlen(B+1)][strlen(C+1)];
}

 

 관련 문제

LCS - 1 페이지