LCS (Longest Common Sequence)

공통 최장 수열, LCS, Longest Common Sequence 라고도 부름

문제 내용

문자열이 하나 주어지고, 그 문자열을 "JENNIFERSOFT" 로 바꿀때 최소 연산 횟수를 출력하라

문제 해결 방법 : 위 문제 풀다가 코드를 올림, LCS 로 공통 최장 수열을 찾고, 공통되지 않은 부분에서의 추가, 삭제의 최대 값을 더하면 답이 나옴

아래의 코드는 다음의 내용이 있음

• LCS 를 통해 공통 최장 수열의 길이를 얻을 수 있다
• path 를 기록해서 공통되거나 추가, 삭제된 부분에 대한 정보를 얻을 수 있다

이 정도면 많이 썼음, 나의 시간은 소중하니까!

훗날 신입이 정리해줄거라 믿고있음

코드

#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

int dy[1002][1002], path[1002][1002];

int lcs(char *a, char *b, int alen, int blen)
{
    int i, j;

    for ( i = 1; i <= alen; i++ )
        for ( j = 1; j <= blen; j++ ) {
            if ( dy[i-1][j] > dy[i][j-1] ) {
                dy[i][j] = dy[i-1][j];
                path[i][j] = 1;
            } else {
                dy[i][j] = dy[i][j-1];
                path[i][j] = 2;
            }

            if ( a[i] == b[j] && dy[i][j] < dy[i-1][j-1] + 1 ) {
                dy[i][j] = dy[i-1][j-1] + 1;
                path[i][j] = 0;
            }
        }

    return dy[alen][blen];
}

int solve(char *a, char *b)
{
    int alen = strlen(a+1), blen = strlen(b+1);
    int i = alen, j = blen, ans = 0, adiff=0, bdiff=0;

    lcs(a, b, alen, blen);

    while ( i > 0 && j > 0 ) {
        switch(path[i][j]) {
            case 0:
                ans += max(adiff, bdiff);
                i--, j--, adiff=0, bdiff=0;
                break;
            case 1:
                i--;
                adiff++;
                break;
            case 2:
                j--;
                bdiff++;
                break;
        }
    }
    while ( i > 0 )
        i--, adiff++;
    while ( j > 0 )
        j--, bdiff++;

    ans += max(adiff, bdiff);
    return ans;
}

int main()
{
    char a[1002], b[1002];

    strcpy(a+1, "JENNIFERSOFT");
    scanf("%s", b+1);
    printf("%d", solve(a, b));

    return 0;
}

정리

신입 님들이 정리해주십쇼

참고자료

신입 님들이 정리해주십쇼

관련문제

신입 님들이 정리해주십쇼