LCS


작성일 : 2017-01-10 19:08:36
조회수 : 492



설명

※이 설명은 공식 솔루션이 아닌 작성자의 개인적인 솔루션입니다.


LCS는 Longest Common Subsequence 의 약자로, 최장 공통 부분 수열을 뜻합니다. 예를들어 ABCD 와 ACD의 LCS는 ACD가 됩니다. 이러한 형태의 LCS는 동적 프로그래밍을 입문할 때 대표격으로 풀어볼 수 있는 문제입니다.


두 개의 문자열 $S$, $T$에 대해 다음과 같은 식이 성립합니다.


  $dp[i][j] =\begin{cases}dp[i-1][j-1]+1,  & \text{S[i]==T[j]} \\max(dp[i-1][j],dp[i][j-1]) & \text{S[i]!=T[j]}\end{cases}$


위의 식은 무슨 뜻일까요? S 문자열의 i번째와, T문자열의 j번째 문자열이 같다면, LCS의 값이 1 증가한다는 뜻이 됩니다. 그 때, 이 문자열을 검사하기 직전의 위치가 S 문자열의 i-1번째와 T문자열의 j-1번째 이므로 이 위치에서 1을 더해주게 됩니다.


만약 같지 않다면, S 문자열에서 하나를 넘겨 검사하거나, T문자열에서 하나를 넘겨 검사해야 할 것입니다. 그리고 그 중, 더 큰 값을 취하면 됩니다. 이 문제를 처음 풀어보시는 분은 적당한 길이의 문자열을 예제로 두고, 손으로 직접 칸을 채워가시면서 풀어보시는 것도 이해에 많은 도움이 됩니다. 

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
string a,b;
int c,d,e[1000][1000]={0};
int main()
{
    cin>>a>>b;
    c=a.length(),d=b.length();
    for(int i=1;i<=c;i++)
        for(int j=1;j<=d;j++)
            if(a[i-1]==b[j-1])e[i][j]=e[i-1][j-1]+1;
            else e[i][j]=max(e[i-1][j],e[i][j-1]);
    cout<<e[c][d];
}

LCS - 알고리즘닷컴
여기서는 https://acmicpc.net 의 문제를 기반으로 한 설명과 소스코드를 포스팅합니다.

36 개의 글