[백준/C++] 9252번: LCS 2

문제

https://www.acmicpc.net/problem/9252

---

문제 요약

두 문자열이 주어졌을 때, 모두의 부분 문자열이 되는 문자열 중 가장 긴 것을 찾아 길이와 함께 출력한다.

---

코드

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>

using namespace std;

// dp[i][j]: 문자열 A에서 i번째 문자까지, 문자열 B에서 j번째 문자까지 봤을 때 LCS 길이
int dp[1010][1010];
string A, B;

int lcs_length;
string res;

int main() {
    cin >> A >> B;

    // LCS 길이 구하기
    for (int i = 1; i <= A.size(); i++) {
        for (int j = 1; j <= B.size(); 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]);
            }
        }
    }

    cout << dp[A.size()][B.size()] << "\n";

    // LCS 문자열 역추적 탐색
    int i = A.size();
    int j = B.size();

    while (i > 0 && j > 0) {
        if (A[i - 1] == B[j - 1]) {
            res += A[i - 1];
            i--;
            j--;
        }
        else if (dp[i - 1][j] > dp[i][j - 1]) {
            i--;
        }
        else {
            j--;
        }
    }

    // 문자열 뒤집기
    reverse(res.begin(), res.end());

    cout << res;

    return 0;
}

---

코드 설명

2차원 Dynamic Programming으로 문제를 해결한다.

 

먼저 LCS의 길이를 구하기 위해 Bottom-Up 방식을 이용한다.

 

두 문자열 A, B의 각 문자를 이중 반복문으로 차례로 접근한다.

 

1. 두 문자가 같다면, 해당 문자 이전까지의 LCS 길이에 1을 더한 값이 해당 문자를 포함한 LCS 길이이다.

=> dp[i][j] = dp[i - 1][j - 1] + 1

 

2. 두 문자가 다르다면, 두 문자열에서 해당 문자 이전까지의 LCS 길이 중 더 긴 값이 LCS길이이다.

=> dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

 

여기서 dp[i][j]는 문자열 A에서 i번째 문자까지, 문자열 B에서 j번째 문자까지 봤을 때 LCS 길이이다.

 

+ 현재 두 문자가 같을 때, 두 문자 앞 글자까지가 공통 문자열이라면 계속 공통 문자열이 이어지기 때문이다.

 

다음은 구한 2차원 dp 배열을 이용해, 실제 LCS를 역추적한다.

 

1. 두 문자열의 끝에서부터 역추적하기 위해 i와 j를 각각 문자열 A와 B의 길이로 초기화한다.

 

2. 역추적을 두 문자열의 처음까지 진행하기 위해 i와 j가 0보다 큰 동안 반복한다.

 

3. 현재 위치의 문자 A[i - 1]과 B[j - 1]이 같다면, LCS의 일부이므로 res에 추가하고, i와 j를 각각 1씩 감소시켜 다음으로 이동한다.

 

4. 현재 위치의 문자 A[i - 1]과 B[j - 1]이 같지 않다면, dp 테이블을 비교하여 큰 쪽으로 이동한다.

 

5. 역추적이 종료됐다면, LCS를 역순으로 추가했기 때문에 res를 뒤집어 정답을 구하고 출력한다.

---

고찰

LCS 길이를 구하는 방법은 알고 있었지만, 역추적하여 LCS 자체를 구하는 것을 알지 못했었다.

 

신기했다..