[백준] 18438 LCS 5 C++

분할 정복을 활용한 LCS 복원 알고리즘

두 문자열 사이의 최장 공통 부분 수열(Longest Common Subsequence, LCS)을 구하는 문제는 전산학에서 매우 중요한 문제 중 하나입니다. 이 글에서는 분할 정복 기법을 활용하여 LCS를 복원하는 효율적인 알고리즘을 소개합니다. 이를 구현한 C++ 코드를 분석하고, 어떻게 동작하는지 하나씩 살펴보겠습니다.

 

1. 문제 정의

주어진 두 문자열 a와 b에 대해:

• 공통으로 존재하는 문자의 순서를 유지하는 가장 긴 부분 수열을 찾아야 합니다.
• 예를 들어, 문자열 a = "ACDBE"와 b = "ABCDE"가 주어지면, 두 문자열의 LCS는 "ACDE"가 됩니다.
•  

2. 코드의 주요 흐름

이 코드는 분할 정복을 사용하여 LCS를 효율적으로 복원합니다. 기존의 동적 계획법(DP)을 활용한 방식(O(n*m))과 비교해 메모리 사용량을 줄이는 동시에 더 큰 입력에서도 효과적으로 동작할 수 있습니다.

2.1. 주요 함수 설명

• lcs(int al, int ar, int bl, int br)
  • 문자열 a[al..ar]와 b[bl..br]에서의 LCS를 찾아 ans에 복원합니다.
  • 이 함수는 다음 과정을 수행합니다:
    1. 문자열을 절반으로 나누어 처리 (중앙 인덱스 활용).
    2. a[al..ah]와 b[bl..br]의 전방 LCS를 계산.
    3. a[ah+1..ar]와 b[bl..br]의 후방 LCS를 계산.
    4. 최적의 분할 지점(인덱스)을 찾아 문제를 두 개로 나누어 재귀적으로 해결.
• 전방 및 후방 LCS 계산
  • LCS1: a[al..ah]와 b[bl..br]에 대해 좌에서 우로 LCS 길이를 계산.
  • LCS2: a[ah+1..ar]와 b[bl..br]에 대해 우에서 좌로 LCS 길이를 계산.
  • 두 값을 합쳐 최적의 분할 지점을 찾습니다.
• 결과 저장
  • LCS에 포함되는 문자를 ans에 저장하며, 최종 결과로 LCS 문자열을 복원합니다.

 

3. 코드 상세 분석

3.1. 초기화

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

string a, b;
string ans;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> a >> b;

    lcs(0, (int)a.size() - 1, 0, (int)b.size() - 1);

    cout << ans.size() << '\n' << ans << '\n';
    return 0;
}

• a와 b를 입력받고, LCS 복원을 위해 lcs()를 호출합니다.
• 최종적으로 LCS의 길이와 LCS 문자열을 출력합니다.

3.2. 분할 정복 함수 lcs

이 함수는 LCS를 구하기 위한 핵심 로직입니다.

• (1) 유효하지 않은 범위 처리

if (bl > br) return;

• (2) 기저 사례 처리

if (al == ar) {
    for (int j = bl; j <= br; ++j) {
        if (a[al] == b[j]) {
            ans += a[al];
            break;
        }
    }
    return;
}

• • 문자열 a의 구간 길이가 1인 경우, 해당 문자가 b 내에서 존재하면 ans에 추가합니다.
• (3) 전방 LCS 계산

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]);
        }
    }
} 

• a[al..ah]와 b[bl..br]의 LCS를 계산하여 LCS1에 저장합니다.
• (4) 후방 LCS 계산

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]);
        }
    }
}

• a[ah+1..ar]와 b[bl..br]의 LCS를 계산하여 LCS2에 저장합니다.

• (5) 최적 분할 지점 찾기 및 재귀 호출

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);

 

 

4. 시간 복잡도

• 이 알고리즘은 분할 정복과 동적 계획법을 결합하여 동작합니다.
• 시간 복잡도는 O(n * m), 하지만 메모리 사용량은 기존의 O(n * m)에서 O(m)으로 감소합니다.

 

5. 전체 코드

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

string a, b;
string ans;

// 분할 정복으로 LCS를 복원하는 함수
void lcs(int al, int ar, int bl, int br) {
    // 범위가 엇갈린 경우(유효하지 않은 경우) 종료
    if (bl > br) return;

    // a 구간 길이가 1인 경우, b[bl..br]에서 a[al]와 같은 문자가 하나라도 있으면 ans에 추가
    if (al == ar) {
        for (int j = bl; j <= br; ++j) {
            if (a[al] == b[j]) {
                ans += a[al];
                break;
            }
        }
        return;
    }

    // a 중앙 인덱스(분할 지점)
    int ah = (al + ar) >> 1;  // 괄호로 감싸서 확실히 중간 인덱스를 구한다

    int n = ar - al + 1;  // a 구간 길이
    int m = br - bl + 1;  // b 구간 길이

    // LCS1[j] : a[al..ah]와 b[bl..(bl+j-1)]의 LCS 길이
    // LCS2[j] : a[ah+1..ar]와 b[(bl+j-1)..br]의 LCS 길이
    // tmp는 계산 과정에서 임시로 사용
    static vector<int> LCS1, LCS2, tmp; 
    LCS1.assign(m + 2, 0);
    LCS2.assign(m + 2, 0);

    // 1) a[al..ah]와 b[bl..br]에 대해 전방 LCS 계산
    for (int i = al; i <= ah; ++i) {
        tmp = LCS1;  // 이전 행(또는 이전 i)에 대한 복사
        for (int j = bl; j <= br; ++j) {
            int rj = j - bl + 1; // LCS1/2 벡터에서의 인덱스
            if (a[i] == b[j]) {
                LCS1[rj] = tmp[rj - 1] + 1;
            } else {
                LCS1[rj] = max(tmp[rj], LCS1[rj - 1]);
            }
        }
    }

    // 2) a[ah+1..ar]와 b[bl..br]에 대해 후방 LCS 계산
    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]);
            }
        }
    }

    // 3) b 구간을 분할할 지점(midx)을 찾는다.
    //    LCS1[j] + LCS2[j+1]이 최대가 되는 j를 찾음
    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;
        }
    }

    // 4) 분할 정복: b 구간을 (bl..bl+midx-1) / (bl+midx..br)로 나누어 처리
    lcs(al, ah, bl, bl + midx - 1);
    lcs(ah + 1, ar, bl + midx, br);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> a >> b;
    // 필요하면 ans.reserve(min(a.size(), b.size()));

    lcs(0, (int)a.size() - 1, 0, (int)b.size() - 1);

    cout << ans.size() << '\n' << ans << '\n';
    return 0;
}