LCS

emplam27 님의 정리 글

LCS는 Longest Common Subsequence의 약자로, 두 문자열에서 최대로 공통되는 부분 중 제일 긴 것을 찾는다. 알고리즘은 평범한 $O(N^2)$ 인 대표 DP 유형이지만, 구현 난이도가 살짝 까다롭기 때문에, 정리해본다.

아래 코드는 흔히 얘기하는 LCS는 아니고, Longest Common Substring을 구하는 코드인데, 최종적으로 구하려고 하는 Longest Common Subsequence보다 구현이 간단하기 때문에 짚고 넘어간다.

for(int a = 1; a <= lena; ++a) {
    for(int b = 1; b <= lenb; ++b) {
        if (A[a] == B[b]) DP[a][b] = DP[a-1][b-1] + 1;
        else DP[i][j] = 0;
    }
}

사실 이 경우에는 굳이 2차원 DP 배열을 쓸 필요도 없다. 1차원으로도 충분하기 때문에.. 다만, 굳이 2차원으로 만든 이유는 관찰을 위해서이다. 이 DP 테이블의 결과를 보게 되면, 중복되는 문자열을 만나게 되면 대각선 우하단 방향으로 이동하는 것을 알 수 있다. 또한, 중간에 서로 다른 문자열이 나오자마자 칼같이 DP 테이블을 0으로 만들어 주는 것이 포인트이다.

여기서 사고를 확장해보자. 0으로 만드는 이유는 연속된다는 조건이 있기 때문이다. 그렇다면 연속된다는 조건이 없을 때는 어떻게 될 것인가? 이 경우 현재까지의 최대 공통 부분 길이가 유지가 되어야 한다. 그리고 이 유지는 x축으로 해야할 수도 있고, y축으로 해야할 수도 있기 때문에 x, y축에 대한 max 값을 구해주면 되겠다. 그래서 위 DP 식이 아주 약간 바뀐다. 이 부분만 수정을 하게 되면, 코드가 Longest Common Subsequence를 구하는 코드로 변하게 된다.

for(int a = 1; a <= lena; ++a) {
    for(int b = 1; b <= lenb; ++b) {
        if (A[a] == B[b]) DP[a][b] = DP[a-1][b-1] + 1;
        else DP[a][b] = max(DP[a-1][b], DP[a][b-1]);
    }
}

잘 동작할까? 이 의문을 해소하기 앞서서, $DP[lena][lenb]$ 로는 가장 긴 LCS의 길이만을 알 수 있을 뿐인데, 만약 이러한 LCS 중 1개를 출력하라는 문제를 만나면 어떻게 풀까? 위 코드가 잘 동작하는지 알아보기 위해 전체적인 구조 이해와 문제 해결을 위해 아래와 같은 DP Table 결과를 예시로 보자. 가로축과 세로축은 각각 abc와 axbycz의 문자열을 할당했고, 이들의 LCS는 $3$ 임을 바로 알 수 있을 것이다.

-	a	b	c
-	0	0	0
a	1	1	1
x	1	1	1
b	1	2	2
y	1	2	2
c	1	2	3
z	1	2	3

LCS를 하나 구하기 위해 우리가 주목해야할 부분은 대각선 이다. 아래와 같은 프로세스로 문자열을 찾는다.

우하단 좌표인 $(lena, lenb)$ 부터 시작한다.
왼쪽 혹은 위쪽으로 숫자가 같은 지점까지 쭉 따라간다.
- 위 표에서는 $(z,c)$ 으로 시작해서, $(c,c)$ 에서 처음으로 멈추게 되겠다.
왼쪽 혹은 위쪽에 더 이상 같은 숫자가 없으면, 좌상단 방향, 즉 $(x - 1, y - 1)$ 좌표에 있는 숫자가 $(x, y)$ 좌표의 숫자보다 $1$ 작은 수가 된다. 그 위치에서의 문자열을 기록하고, 대각선 방향으로 이동한다.
이를 반복하여 최종적으로 숫자가 0이 될 때까지 저장된 문자열을 읽으면, 그것이 LCS가 된다.

2번이 조금 이해가 안될 수 있는데, 맨 처음 코드를 다시 올려보면, 문자열이 같을 때 $(x+1, y+1)$ 방향으로 1만큼 더하면서 전진했다. 이를 역으로 한 것이라고 보면 된다.

예시 구현 코드

AtCoder Educational DP Contest F번: https://atcoder.jp/contests/dp/tasks/dp_f

두 문자열을 받아 가장 긴 LCS를 출력하는 문제이다.

char A[3010];
char B[3010];
char C[3010];
int DP[3010][3010];

void solve() {
    scanf("%s %s", &A[1], &B[1]);
    int lena = strlen(&A[1]);
    int lenb = strlen(&B[1]);

    for(int b = 1; b <= lenb; ++b) {
        for(int a = 1; a <= lena; ++a) {
            if (A[a] == B[b]) {
                DP[b][a] = DP[b - 1][a - 1] + 1;
            } else {
                DP[b][a] = max(DP[b - 1][a], DP[b][a - 1]);
            }
        }
    }

    // LCS 길이 = DP[lenb][lena]
    int ca = lena, cb = lenb;
    int cp = 0;
    while(DP[cb][ca] != 0) {
        if (DP[cb - 1][ca] == DP[cb][ca]) {
            --cb;
        } else if (DP[cb][ca - 1] == DP[cb][ca]) {
            --ca;
        } else if (DP[cb - 1][ca - 1] + 1 == DP[cb][ca]) {
            C[cp++] = B[cb];
            cb--; ca--;
        }
    }
    int clen = cp;
    for(int i = cp - 1; i >= 0; --i) { // 출력은 역순으로
        printf("%c", C[i]);
    }
    printf("\n");
}