화투의 개발 블로그

[문제 링크]

LCS2는 다음 포스트에 있는 내용과 같다.

http://hsp1116.tistory.com/37

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
vector<char> output;
int cache[1001][1001];
char input[1001],compare[1000];
int LCS(int m,int n){
    memset(cache,0,sizeof(cache));
    for(int i=1;i<=m;i++){
        for(int j=1; j<=n;j++){
            if(compare[i-1] == input[j-1]){
                cache[i][j] = cache[i-1][j-1] +1;
                }
            else{
                cache[i][j] = std::max(cache[i-1][j], cache[i][j-1]);
            }
        }
    }
    return cache[m][n];
}
void backTracking(int m, int n){
    if(m==0 || n ==0) return;
    if(cache[m][n] > cache[m-1][n-1] && cache[m][n] > cache[m][n-1] && cache[m][n] > cache[m-1][n]){
        output.push_back(input[n-1]);
        backTracking(m-1, n-1);
    }else if(cache[m][n] > cache[m-1][n] && cache[m][n] == cache[m][n-1]){
        backTracking(m, n-1);
    }else{
          backTracking(m-1, n);
    }
}
int main(){
    scanf("%s%s",input,compare);
    int m = strlen(compare), n = strlen(input);
    printf("%d\n",LCS(m,n));
    backTracking(m,n);
    for(int i=output.size()-1;i>=0;i--)
        printf("%c",output[i]);
}

[문제 링크]

LCS는 다음 포스트에 있는 내용과 같다.

http://hsp1116.tistory.com/37

#include <cstdio>
#include <algorithm>
#include <cstring>
int cache[1001][1001];
char input[1001],compare[1000];
int LCS(){
    int n = strlen(compare), m = strlen(input);
    memset(cache,0,sizeof(cache));
    for(int i=1;i<=n;i++){
        for(int j=1; j<=m;j++){
            if(compare[i-1] == input[j-1]){
                cache[i][j] = cache[i-1][j-1] +1;
                }
            else{
                cache[i][j] = std::max(cache[i-1][j], cache[i][j-1]);
            }
        }
    }
    return cache[n][m];
}
int main(){
    scanf("%s %s",input,compare);
    printf("%d\n",LCS());
}

공통 부분 수열이란, 두 문자열이 공통으로 가지고 있는 부분 수열을 말한다.

예를 들어 문자열

문자열 A : CDABE

문자열 B : CDEGT

가 있다면,

공통 부분 수열은

{},{C},{D},{E},{C,D},{D,E},{C,E},{C,D,E}

일 것이다.

1. 최장 공통 부분 수열 길이 구하기

최장 공통 부분 수열은 공통 부분 수열 중에서 길이가 가장 긴 부분 수열을 말한다.

위 예제 최장 공통 부분 수열은{C,D,E}이고, 길이가 3이다.

최장 증가 부분 수열은 또한 다음과 같은 정의를 따른다. 각 점화식을 에제를 들어 확인해보자.

(1) Ai != Bj

두 문자열 CDABE,CDEGT의 최장 공통 부분 수열을 구한다고 해보자.

여기서 맨 마지막 문자인 E와 T가 각각 다르므로 다음과 같은 경우를 고려 할 수 있다.

1. 최장공통부분 수열이 E로 끝나는 경우.

이 경우 K는 최장 공통 부분 수열에 아무련 영향을 끼치지 않으므로 없어도 상관 없다.

즉 LCS(i,j) = LCS(i,j-1)이다.

2. 최장 공통 부분 수열이 T로 끝나는경우

이 경우 E가 최장 공통 부분 수열에 아무런 영향을 끼치지 않으므로 지워도 상관없다.

이 경우엔 LCXS(i,j) = LCS(i-1,j)이다 

3. 둘 다 해당이 되지 않는 경우.

둘 다 지워도, 하나만 지워도 최장 증가 부분 수열에 영향을 끼치지 않는다. 따라서 고려 할 필요가 없다.

두 문자가 일치하지 않을 때, 최소 둘 중 하나는 최장 공통 부분 수열에 영향을 끼치지 않으므로 둘 중 하나를 지워도 상관없다.

즉 둘 중 하나를 지웠을 때의 더 큰 LCS가 LCS(i,j)이다.

따라서 LCX(i,j) = max(LCS(i-1,j),LCS(i,j-1))임을 알 수 있다.

(2) Ai == Bj

두 문자열 CDABE CDE라고 가정해보자. 맨 뒤의 문자 E가 설 일치하는데, 공통 문자인 E는 최장 공통 부분 수열에 반드시 포함될 것이다.

따라서 이 두 문자열을 지운다면, 최장 공통 부분 수열에서 또한 E가 사라질 것이라는 것을 알 수 있다.

즉 최장 증가 부분 수열의 길이 또한 1 감소하므로, LCX(i,j) = LCS(i-1,j-1) + 1이다.

이제 위 공식을 이용하여 구현하면 된다. 각 인덱스는 현재 문자열의 길이라고 생각하면 된다.

맨첨 1행, 1열들은 모두 0으로 치워지는데 이는 빈 수열을 뜻한다. 빈 수열과 문자열의 최장 증가 부분 수열은 0이기 때문이다.

밑은 앞서 확인한 공식으로 작성한 테이블이다.

LCS(5,5)=3으로, 최장 공통 부분 수열의 길이는 3임을 알 수 있다.

int LCS(string& input, string& compare){
    int cache[1001][1001];
    memset(cache,0,sizeof(cache));
    for(int i=1;i<=compare.length();i++){
        for(int j=1; j<=input.length();j++){
            if(compare[i-1] == input[j-1]){
                cache[i][j] = cache[i-1][j-1] +1;
                }
            else{
                cache[i][j] = max(cache[i-1][j], cache[i][j-1]);
            }
        }
    }
    return cache[compare.length()][input.length()];
}

1. 최장 공통 부분 수열 구하기

이는 우리가 구한 2차원 배열을 역추적 하여 구할 수 있다.

최장 증가 부분 수열을 찾는 공식을 잘 고려해 보자.

우리가 찾아야 하는건 Ai == Bi인 문자이다.

Ai == Bj일 때 LCS(i,j) = LCS(i-1,j-1) + 1였는데. 이를 고려해 역추적 해나가면 된다.

다만 또 고려할 것이 있는데, LCX(i,j) = max(LCS(i-1,j),LCS(i,j-1))의 경우이다.

Ai != Bj일 지라도, LCS(i,j) = max(LCS(i-1,j),LCS(i,j-1))를 통해 LCS(i-1,j-1) + 1가 도출 될 수 있다.

따라서 LCS(i-1,j), LCS(i,j-1)이 둘 다 LCS(i,j)보다 작으면서, LCS(i-1,j-1)이 LCS(i,j)보다 작은 경우가 Ai==Bj일 때이다. 

즉 LCS[i][j] > LCS[i-1][j-1] && LCS[i][j] > LCS[i][j-1] && LCS[i][j] > LCS[i-1][j])를 조건으로 코드를 구현하면 된다.

밑은 해당 코드이며, output에 최장 공통 부분 수열 문자열이 저장된다.

string output;
void backTracking(int m, int n){
    if(m==0 || n ==0) return;
    if(cache[m][n] > cache[m-1][n-1] && cache[m][n] > cache[m][n-1] && cache[m][n] > cache[m-1][n]){
        //문자열 인덱스는 캐시 인덱스보다 1씩 더 작다. 
        output = input[n-1] + output;
        backTracking(m-1, n-1);
    }else if(cache[m][n] > cache[m-1][n] && cache[m][n] == cache[m][n-1]){
        backTracking(m, n-1);
    }else{
          backTracking(m-1, n);
    }
}