[C++ 알고리즘] LCS, Longest Common Subsequence

개요

LCS(Longest Common Subsequence)는 최장 공통 부분 수열로, 두 문자열 사이 공통되는 부분을 말한다. 즉 문자열의 상대적인 순서만 같으면 된다.

예를들어 아래와 같이 2개의 문자열이 있을 때

LCS는 ABCCE이다. 

이런 LCS는 DP를 활용해서 구한다.

과정

먼저 AABCCDE와 A의 공통부분을 구한다고 가정해보자. 표에는 현재까지 가장 긴 공통부분의 길이를 저장할 것이다. 그러면 표는 아래와 같이 된다. (A는 길이가 1이니 최대 공통부분의 길이는 1이다.)

이제 AABCCDE와 AB의 최장공통부분수열의 길이를 구해보도록 하자. 그러면 아래와 같이 될 것이다.

여기서 주목해야 하는 부분은 공통되는 부분인 B가 나왔을 때이다. 저곳은 AAB와 AB의 LCS의 길이를 기록한 부분인데 AB가 공통수열이 된다. 우리는 이것을 눈으로 보면 알 수 있지만 dp의 관점에서 생각해보도록 하자.

AAB와 AB의 LCS가 AB라는 것은 다른말로 AA와 A의 LCS인 A에 B를 추가한 것이다. 즉 같은 문자를 찾았을 때의 점화식은 아래와 같다.

// 같은 문자를 만났을 때
dp(i-1)(j-1) + 1

그럼 일치하지 않는다면 어떻게 될까? 이 부분을 이해하기 위해 다음 단계인 AABC와 AB의 LCS를 찾아보도록 하자. 이것 역시 우리는 AB라는 것을 알고 있고, 2가 기록되어야 한다는 것을 알고있다.

즉 AABC와 AB의 LCS는 AABC와 A의 LCS, AAB와 AB의 LCS중 긴 것과 같다. 그렇기에 AB의 길이인 2를 기록한다.

C에 대해서도 채우면 아래와 같이 된다. 값이 같을 때에는 대각선에서 가져오고, 값이 다를 때에는 여태까지의 LCS중 긴 것을 가져오는 것이다.

이런방식으로 표를 쭉 채워나가면 아래와 같이 된다. 앞서 구한 LCS ABCCE의 길이 5가 나왔다.

 

코드

이것을 코드로 구현하면 아래와 같다.

#include <iostream>
#include <algorithm>
using namespace std;

int dp[1001][1001];

int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);
    string s1,s2;
    cin>>s1>>s2;

    int s1Len=s1.length();
    int s2Len=s2.length();

    for(int i=1;i<=s1Len;i++){
        for(int j=1;j<=s2Len;j++){
            char curChar1=s1[i-1];
            char curChar2=s2[j-1];

            if(curChar1==curChar2){
                dp[i][j]=dp[i-1][j-1]+1;
            }else{
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        }
    }
    
    cout<<dp[s1Len][s2Len];
}

 

연습문제

https://www.acmicpc.net/problem/9251