[Baekjoon,9252]LCS 2

해결

LCS 길이 구하기

먼저 두 문자열의 최장 공통 부분 수열의 길이를 구하는 것이 우선이다. 구하는 방법은 문자열을 한 글자씩 확인하며 일치하는 경우 두 문자열 모두 다음 문자로 이동하고, 일치하지 않으면 둘 중 하나만 다음 문자로 이동한다. 이를 동적 계획법에 적용하면 반복하여 계산하는 부분을 없애 해결할 수 있다.

예를 들어 ACAYKP와 CAPCAK가 있다고 할 때 아래와 같은 과정을 거치면 된다.

[ACAYKP]
[CAPCAK]
첫 번째 인덱스들이 일치하지 않으므로 두 인덱스를 각각 다음 단계로 넘어간다.

[ACAYKP] [ACAYKP]
[CAPCAK] [CAPCAK]
넘어간 인덱스 들이 일치한다. 그러므로 둘 다 다음 단계로 한꺼번에 넘어간다.
그리고 현재 위치 apos와 bpos가 있을 때 cache[apos][bpos]를 1 증가시켜 다음 함수를 호출한다.

[ACAYKP] [ACAYKP]
[CAPCAK] [CAPCAK]
범위가 벗어날 때까지 반복한다.

위와 같은 과정을 함수로 구현하면 아래와 같다.

string a,b;
int cache[MAX][MAX];
int solve(int apos, int bpos)
{
    if(apos>=a.size() || bpos>=b.size())
        return 0;
    
    int& ret=cache[apos][bpos];
    if(ret!=-1)
        return ret;
    
    if(a[apos]==b[bpos])
        return ret=solve(apos+1,bpos+1)+1;
    
    return ret=max(solve(apos,bpos+1),solve(apos+1,bpos));
}

문자열 리모델링 하기

이제 남은건 LCS인 문자열을 만드는 것이다. 방금 했던 과정을 다시 하는데 다른 점이 있다.

• apos 와 bpos에 대해 두 문자가 같으면 현재 문자를 결과 문자열에 더한다.
• 다르다면 각각 다음 인덱스에 대해 만들어진 cache값이 더 큰 쪽으로 향한다. 즉, LCS인 방향으로 가는 것이다.

이에 대한 구현은 아래와 같다.

string s;
void reconstruct(int apos, int bpos)
{
    if(apos>=a.size() || bpos>=b.size())
        return;
    
    if(a[apos]==b[bpos])
    {
        s+=a[apos];
        reconstruct(apos+1,bpos+1);
    }
    // apos+1 로 가는 것이 lcs일 때 
    else if(cache[apos+1][bpos]>=cache[apos][bpos+1])
        reconstruct(apos+1,bpos);
    // bpos+1 로 가는 것이 lcs일 때
    else
        reconstruct(apos,bpos+1);
}

구현

#include <iostream>
#include <string>
#include <cstring>
using namespace std;

const int MAX=1001;

string a,b,s;
int cache[MAX][MAX];

int solve(int apos, int bpos)
{
    if(apos>=a.size() || bpos>=b.size())
        return 0;
    
    int& ret=cache[apos][bpos];
    if(ret!=-1)
        return ret;
    
    if(a[apos]==b[bpos])
        return ret=solve(apos+1,bpos+1)+1;
    
    return ret=max(solve(apos,bpos+1),solve(apos+1,bpos));
}

void reconstruct(int apos, int bpos)
{
    if(apos>=a.size() || bpos>=b.size())
        return;
    
    if(a[apos]==b[bpos])
    {
        s+=a[apos];
        reconstruct(apos+1,bpos+1);
    }
    // a의 다음 문자로 가는 것이 결과 값일 때 
    else if(cache[apos+1][bpos]>=cache[apos][bpos+1])
        reconstruct(apos+1,bpos);
    else
        reconstruct(apos,bpos+1);
}

int main()
{
    cin>>a>>b;
    memset(cache,-1,sizeof(cache));

    int lcs=solve(0,0);
    s="";
    reconstruct(0,0);
    cout<<lcs<<endl;
    cout<<s<<endl;
    return 0;
}