백준 18438번 - LCS 5

LCS 5 (백준 18438번)

개념 : LCS

난이도 :

링크 : LCS 5 : https://www.acmicpc.net/problem/18438

---

접근

해당 $LCS$ 문제는 $LCS 2$ 문제와 완전히 같지만 오로지 메모리 제한만이 다르다. 이 문제를 해결하기 위해서는 히르쉬버그 알고리즘 이라는 동적 계획법 최적화를 알고 있어야 한다.

히르쉬버그 알고리즘을 사용하기 위해서는, 상태 전이 간선을 DAG(Directed Acyclic Graph)로 바라볼 수 있어야하고, 토글링 방식으로 문제를 해결할 수 있어야한다.

Direct Acyclic Graph (Alves, C. E. R., Cáceres, E. N., & Song, S. W. (2008). An all-substrings common subsequence algorithm. Discrete Applied Mathematics, 156(7), 1025-1035.)

두 문자열 $A$, $B$가 있고 각각의 길이를 $N, M$이라고 하고, $(0, 0) \dots (N, M)$ 까지의 $(N+1) \times (M+1)$개의 정점이 있다고 하자.

$LCS$는 가중치 0, 1을 갖는 DAG 그래프에서 최장거리를 구하는 것으로 바꿀 수 있다.

• $(i, j-1) \rightarrow (i, j)$
• $(i-1, j) \rightarrow (i, j)$

두 방향의 간선은 임의의 $i$, $j$에 대해 존재할 수 있고 가중치는 0이다.

• $(i-1, j-1) \rightarrow (i, j)$

대각선 방향의 간선은 $A[i] = B[j]$인 경우에 존재할 수 있으며 가중치는 1이다.

이렇게 $DAG$를 구성하면, $LCS$문제는 $(0, 0) \rightarrow (N, M)$의 최장거리 구하기 문제로 바뀌게 된다.

그리고 여기서 다음과 같은 관찰을 해보자.

1. $(0, 0) \rightarrow (N, M)$ 최장경로는 반드시 $i$행의 점 중 하나를 지나야만 한다.
2. 해당 점을 $(i, j’)$라고 하면, $(0, 0) \rightarrow (i, j’) \rightarrow (N, M)$ 경로의 길이는 $(i, 0) \dots (i, M)$ 에 대해 최댓값이다.

그래프가 $DAG$이고 우, 하, 우하 세 방향으로 1칸씩만 이동하므로 경로는 반드시 $i$행의 하나의 점을 지나야만 하므로 1은 증명완료.

그리고 2가 성립하지 않는다면, 그 경로가 최장경로가 되므로, 귀류법으로써 증명완료.

$i = N / 2$ 라고 하고, 최장경로가 해당 행을 지나는 점의 열을 $j’$라고 하자. 이제 전체 $LCS$는 $LCS(A[1 \dots i], B[1 \dots j’]) + LCS(A[i+1 \dots N], B[j’+1 \dots M])$가 된다.

이는 분할 정복으로 이어질 수 있다는 점을 바로 이해할 수 있을 것이다. 더 이상 나뉠 수 없을만큼 분할, 즉 문자가 1개만 남은 것과의 $LCS$를 구하는 것은 매우 쉽기 때문에, 전체 $LCS$문자열까지 구할 수 있게 된다.

알고리즘의 핵심은 $j’$를 구하는 것이다. 이는 $(0, 0) \rightarrow (i, j)$와 $(N, M) \rightarrow (i, j)$ 두 경로의 길이 합의 최댓값을 갖는 $j$를 구하여 해결할 수 있다.

$DIST((x, y), (i, j))$를 $(x, y) \rightarrow (i, j)$로 가는 최장거리라고 하자.

이를 위해서 $LCS(A[1 \dots i], B[1 \dots M])$를 구할 수 있는 $DP$ 테이블을 만들며, $LCS(A[N \dots i+1], B[M \dots 1])$를 구하는 $DP$ 테이블을 만들면 모든 $DIST((0, 0) \rightarrow (i, j)) + DIST((N, M) \rightarrow (i, j))$ 값을 구할 수 있다. 이 과정이 $LCS$의 길이만 있으면 되기 때문에 토글링방식으로 구할 수 있고, 메모리를 매우 축소하는 과정이 된다.

매 분할 정복 과정마다 배열의 크기가 아주 대략 각각 절반씩 줄어들기 때문에 시간복잡도는 다음과 같이 구해진다. 엄밀한 증명은 아님을 감안하고 보길 바란다.

\[NM + 2 \times {NM \over 4} + 2 ^ 2 \times {NM \over 4^2} + \dots \in O(NM)\]

약간의 오버헤드는 있지만, 시간복잡도는 대략 $O(NM)$이 된다. 공간복잡도는 토글링시 가장 많이 사용하는 1단계 재귀만 파악하면 된다. $O(max(N, M))$만 있으면 된다.

#include <bits/stdc++.h>

using namespace std;

string a, b;
string ans;


void lcs(int al, int ar, int bl, int br) {
    if (bl > br) return;
    if (al == ar) {
        for (int i=bl; i<=br; ++i) if (a[al] == b[i]) {
            ans += a[al];
            break;
        } 
        return;
    }


    int n = ar - al + 1;
    int m = br - bl + 1;

    int ah = al + ar >> 1;
    vector<int> LCS1(m + 2), LCS2(m + 2), tmp;
    for (int i=al; i<=ah; ++i) {
        tmp = LCS1;
        for (int j=bl; j<=br; ++j) {
            int rj = j - bl + 1;
            if (a[i] == b[j]) LCS1[rj] = tmp[rj-1] + 1;
            else LCS1[rj] = max(tmp[rj], LCS1[rj-1]);
        }
    }


    for (int i=ar; i>ah; --i) {
        tmp = LCS2;
        for (int j=br; j>=bl; --j) {
            int rj = j - bl + 1;
            if (a[i] == b[j]) LCS2[rj] = tmp[rj+1] + 1;
            else LCS2[rj] = max(tmp[rj], LCS2[rj+1]);
        }
    }   
    
    int mxlcs = -1, midx = 0;
    for (int j=0; j<=m; ++j) {
        if (LCS1[j] + LCS2[j+1] > mxlcs) {
            mxlcs = LCS1[j] + LCS2[j+1];
            midx = j;
        }
    }

    lcs(al, ah, bl, bl+midx-1);
    lcs(ah+1, ar, bl+midx, br);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> a >> b;
    lcs(0, a.size()-1, 0, b.size()-1);
    cout << ans.size() << '\n' << ans;
}

reference :

박진한님 블로그 : lcs 5