Algorithms/DP Applications

2.16.3 LCS

개념

LCS는 두 수열에 공통으로 나타나는 부분 수열 중 가장 긴 것입니다. 각 수열에서 원래 순서를 지키며 원소를 고르고, 연속할 필요는 없습니다.

ABCBDAB와 BDCABA의 공통 부분 수열 중 BCBA의 길이는 44입니다.

상태와 점화식

Di,jD_{i,j}는 첫 문자열의 앞 ii글자와 둘째 문자열의 앞 jj글자의 LCS 길이입니다. 한쪽이 빈 문자열이면 LCS 길이는 00입니다.

마지막 글자가 같으면 두 글자를 함께 선택하여 Di,j=Di−1,j−1+1D_{i,j}=D_{i-1,j-1}+1입니다. 다르면 둘 중 한 글자를 제외한 최댓값 max⁡(Di−1,j,Di,j−1)\max(D_{i-1,j},D_{i,j-1})을 사용합니다.

마지막 글자가 같으면, 그 앞부분의 공통 부분 수열 뒤에 같은 글자를 붙일 수 있습니다. 마지막 글자가 다르면 두 글자를 한 쌍으로 선택할 수 없으므로 적어도 한쪽의 마지막 글자를 제외해야 합니다. 두 제외 방법을 모두 비교하면 더 긴 쪽을 찾을 수 있습니다.

AB와 ACB의 경우, 앞부분 A와 AC의 LCS는 A로 길이가 11입니다. 마지막 B가 같으므로 이를 붙여 AB를 얻고 길이는 22가 됩니다.

첫 문자열의 앞부분 / 둘째 문자열의 앞부분빈 문자열AACACB
빈 문자열00000000
A00111111
AB00111122

원소의 값이 증가하는 LIS와 달리, LCS는 두 수열에서 공통으로 선택할 수 있는 순서를 비교합니다. 문자 사이에 다른 문자가 있어도 선택할 수 있으므로 연속된 공통 문자열을 찾는 문제와도 구분합니다. 두 문자열이 각각 길이 10001000이면 약 100100만 칸, 각각 1000010000이면 약 11억 칸을 계산하므로 두 길이의 곱을 확인합니다.

DP 표에서 역추적

길이를 계산한 표에서 마지막 칸 DN,MD_{N,M}부터 이동하면 실제 LCS를 구할 수 있습니다. 현재 위치를 (i,j)(i,j)라고 할 때, 두 문자열의 마지막 문자인 AA의 ii번째 문자와 BB의 jj번째 문자를 비교합니다.

조건선택과 이동이유
두 문자가 같음그 문자를 답에 추가하고 (i−1,j−1)(i-1,j-1)로 이동두 문자를 함께 선택하여 길이가 11 증가한 칸
두 문자가 다르고 Di−1,j≥Di,j−1D_{i-1,j}\ge D_{i,j-1}(i−1,j)(i-1,j)로 이동첫 문자열의 마지막 문자를 제외해도 최적 길이를 유지
두 문자가 다르고 Di−1,j<Di,j−1D_{i-1,j}<D_{i,j-1}(i,j−1)(i,j-1)로 이동둘째 문자열의 마지막 문자를 제외해도 최적 길이를 유지

두 문자가 다를 때 위쪽과 왼쪽의 길이가 같으면 어느 쪽으로 이동해도 하나의 LCS를 얻습니다. 이 설명에서는 위쪽으로 이동합니다. 이동만 하는 단계에서는 답에 문자를 넣지 않습니다.

i=0i=0 또는 j=0j=0이면 한쪽 문자열의 앞부분이 비었으므로 역추적을 끝냅니다. 뒤쪽 문자부터 골랐으므로 모은 문자들의 순서를 뒤집어 출력합니다.

역추적 과정 따라가기

앞의 AB와 ACB의 표에서 오른쪽 아래 칸 (2,3)(2,3)부터 시작합니다.

위치비교할 문자행동지금까지 모은 문자
(2,3)(2,3)B, BB 선택, (1,2)(1,2)로 이동B
(1,2)(1,2)A, C위의 값 00보다 왼쪽 값 11이 크므로 (1,1)(1,1)로 이동B
(1,1)(1,1)A, AA 선택, (0,0)(0,0)으로 이동BA

모은 BA를 뒤집으면 AB입니다. 두 문자열에서 원래 순서대로 나타나며, 계산한 최적 길이 22와도 일치합니다.

AB와 BA처럼 LCS가 여러 개일 수도 있습니다. (2,2)(2,2)에서 문자는 다르고 위·왼쪽 값이 모두 11입니다. 위로 이동하면 A, 왼쪽으로 이동하면 B를 얻으며 둘 다 올바른 LCS입니다.

복잡도

더 짧은 앞부분의 답이 준비되도록 행·열 인덱스가 작은 칸부터 표를 채웁니다. 두 문자열의 길이를 N,MN,M이라고 합니다.

연산시간복잡도공간복잡도
LCS DPO(NM)O(NM)DP 표 O(NM)O(NM)
DP 표의 역추적O(N+M)O(N+M)결과 저장 O(min⁡(N,M))O(\min(N,M))

역추적할 때마다 행 또는 열 인덱스가 감소하므로 이동 횟수는 최대 N+MN+M입니다. 길이만 구한다면 이전 행과 현재 행만 저장할 수 있지만, 여기서는 역추적할 때 이전 칸의 값을 확인하도록 전체 표를 저장합니다.

예제

문제

두 문자열의 최장 공통 부분 수열의 길이와 그에 해당하는 문자열 하나를 구하여라.

입력

첫째 줄에 문자열 AA가 주어진다. AA는 영어 대문자로 이루어져 있으며 길이는 11 이상 100100 이하이다.

둘째 줄에 문자열 BB가 주어진다. BB는 영어 대문자로 이루어져 있으며 길이는 11 이상 100100 이하이다.

출력

첫째 줄에 LCS의 길이를 출력한다. 둘째 줄에 LCS를 출력한다. 가능한 LCS가 여러 개이면 그중 하나를 출력한다. 길이가 00이면 둘째 줄은 빈 줄로 출력한다.

예제 입력

ABCBDAB
BDCABA

예제 출력

4
BCBA

예제 코드

C++20

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

int dp[101][101];

int main() {
    int n, m, i, j;
    // dp[i][j]: 두 문자열의 앞 i개와 앞 j개 문자로 만든 LCS 길이
    string a, b, ans;

    cin >> a >> b;
    n = a.size();
    m = b.size();

    for (i = 1; i <= n; ++i) {
        for (j = 1; j <= m; ++j) {
            // 문자가 같으면 두 문자열에서 함께 선택
            if (a[i - 1] == b[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
            else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }

    // 마지막 칸에서 문자를 선택하거나 길이가 유지되는 칸으로 이동
    i = n;
    j = m;
    while (i > 0 && j > 0) {
        // 문자가 같으면 두 문자열에서 함께 선택
        if (a[i - 1] == b[j - 1]) {
            ans += a[i - 1];
            --i;
            --j;
        }
        else if (dp[i - 1][j] >= dp[i][j - 1]) --i;
        else --j;
    }
    // 뒤에서부터 모은 문자를 뒤집어 원래 순서 복원
    reverse(ans.begin(), ans.end());

    cout << dp[n][m] << '\n';
    cout << ans << '\n';
}