Gold IV 난이도 문제를 C++로 풀이한 내용입니다. 두 문자열의 최장 공통 부분 수열(LCS)의 길이를 구하는 문제입니다.

백준 9251: LCS

Gold IV 난이도 문제를 C++로 풀이한 내용입니다. 두 문자열의 최장 공통 부분 수열(LCS)의 길이를 구하는 문제입니다.

문제 소개

문제 번호: 9251
문제명: LCS
난이도 (티어): Gold IV
사용 언어: C++
실행 시간: 4 ms
메모리: 6004 KB
문제 요약: 두 개의 문자열이 주어졌을 때, 두 문자열 모두의 부분 문자열이 되는 가장 긴 문자열을 찾는 문제입니다. 여기서 부분 문자열은 원래 문자열에서 몇 개의 문자를 삭제해도 원래 순서가 유지되는 것을 의미합니다.

접근 방법

문제를 처음 접했을 때, 두 문자열의 모든 부분 문자열을 직접 생성하여 비교하는 것은 시간 복잡도가 매우 높아 현실적인 해결책이 아니라고 판단했습니다. 문자열의 길이가 최대 1000까지 주어지므로 O(N^2) 또는 O(N^3) 정도의 복잡도를 가진 알고리즘이 필요할 것으로 예상했습니다.

이러한 부분 문제 해결 및 최적화 문제에는 동적 계획법(Dynamic Programming, DP)이 효과적이라는 것을 알고 있었습니다. DP를 활용하여 두 문자열의 공통 부분 수열을 점진적으로 찾아나가는 방식을 사용했습니다.

DP 테이블 dp[i][j]는 첫 번째 문자열의 i번째 문자까지와 두 번째 문자열의 j번째 문자까지를 고려했을 때의 최장 공통 부분 수열의 길이를 저장하도록 설계했습니다.

풀이 과정

입력: 두 문자열 str1과 str2를 입력받습니다.
DP 테이블 초기화: dp 테이블을 (n+1) x (m+1) 크기로 생성하고 모든 값을 0으로 초기화합니다. 여기서 n은 str1의 길이, m은 str2의 길이입니다. 테이블 크기를 n+1과 m+1로 하는 이유는 1-indexed 방식으로 DP를 진행하여 첫 번째 문자를 처리할 때 인덱스 오류를 방지하고, dp[0][j]나 dp[i][0]이 0이 되어 다른 경우의 계산에 영향을 주지 않도록 하기 위함입니다.
DP 테이블 채우기:
- str1의 i-1번째 문자와 str2의 j-1번째 문자를 비교합니다. (DP 테이블은 1-indexed, 문자열은 0-indexed이므로 i-1, j-1 사용)
- 문자가 같은 경우: str1[i-1] == str2[j-1]이면, 현재 문자가 공통 부분 수열에 추가될 수 있음을 의미합니다. 따라서 dp[i][j]는 대각선 이전 값인 dp[i-1][j-1]에 1을 더한 값이 됩니다. 이는 현재 문자를 포함하여 LCS 길이가 1 증가했음을 나타냅니다.
- 문자가 다른 경우: str1[i-1] != str2[j-1]이면, 현재 문자는 공통 부분 수열에 포함되지 않습니다. 이 경우, str1의 i-1번째 문자까지와 str2의 j번째 문자까지의 LCS (dp[i][j-1]) 또는 str1의 i번째 문자까지와 str2의 j-1번째 문자까지의 LCS (dp[i-1][j]) 중 더 긴 값을 dp[i][j]로 선택합니다. 이는 현재 문자를 제외하고 이전까지의 최적해를 계승하는 과정입니다.
결과 출력: DP 테이블을 모두 채운 후, dp[n][m]에 저장된 값이 두 문자열 전체에 대한 최장 공통 부분 수열의 길이가 됩니다. 이 값을 출력합니다.

핵심 아이디어: 두 문자열을 순차적으로 비교하며, 현재 문자가 일치하면 이전 최장 공통 부분 수열에 1을 더하고, 불일치하면 이전까지의 최장 공통 부분 수열 중 더 긴 것을 선택하여 부분 문제의 최적해를 합쳐 나가는 방식입니다.

주의할 점:

DP 테이블의 인덱스와 문자열의 인덱스 관리에 주의해야 합니다. DP 테이블은 1-indexed로, 문자열은 0-indexed로 접근합니다.
ios_base::sync_with_stdio(false);와 cin.tie(NULL);을 사용하여 입출력 속도를 향상시켜 시간 초과를 방지했습니다.

코드 설명

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    // 표준 입출력 속도 향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    // 두 문자열 입력받기
    string str1, str2;
    cin >> str1 >> str2;
    
    int n = str1.length();
    int m = str2.length();
    
    // dp[i][j] = str1의 i번째까지, str2의 j번째까지 봤을 때 최장공통부분수열의 길이
    // 1-indexed로 시작 (가비지값 방지, 대각선 위 참조 시 0으로 초기화된 값 사용)
    // dp 테이블 크기를 (n+1) x (m+1)로 하여 0번째 인덱스를 비워두고 1부터 사용
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    
    // 계산 순서: 왼쪽에서 오른쪽, 위에서 아래로
    // (부분수열의 순서 조건 유지)
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            // str1의 i-1번째 문자와 str2의 j-1번째 문자를 비교
            if (str1[i-1] == str2[j-1]) {
                // 같은 문자: dp[i-1][j-1] + 1
                // 현재 문자가 공통 부분 수열에 포함될 수 있으므로,
                // 이전까지의 LCS 길이에 1을 더함 (대각선 왼쪽 위에서 옴)
                // (i,j)에서 이어붙을 수 있는 유일한 이전 칸 = 왼대각위
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                // 다른 문자: max(dp[i-1][j], dp[i][j-1])
                // 현재 문자가 공통 부분 수열에 포함되지 않으므로,
                // 이전까지의 LCS 중 더 긴 것을 선택 (위쪽 또는 왼쪽에서 옴)
                // 어느 경로가 더 긴지 모르므로 max 선택
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
            }
        }
    }
    
    // 최종 답: dp[n][m]
    // 두 문자열 전체를 고려했을 때의 LCS 길이
    // 왜? 모든 칸에서 공통/비공통 기준으로 실처럼 이전 참조하며 갱신
    // → 자동으로 최적에 도달 (전역최적 보장)
    cout << dp[n][m];
    
    return 0;
}

복잡도 분석

시간 복잡도: O(N * M)
- 두 개의 문자열 길이를 각각 N, M이라고 할 때, N x M 크기의 DP 테이블을 한 번씩 방문하여 연산을 수행합니다. 각 셀에서의 연산은 상수 시간 O(1)이므로, 전체 시간 복잡도는 O(N * M)입니다.
공간 복잡도: O(N * M)
- N x M 크기의 DP 테이블을 저장하기 위한 공간이 필요합니다.

배운 점

이 문제를 통해 동적 계획법의 기본 원리를 다시 한번 확실히 이해할 수 있었습니다. 부분 문제의 최적해를 이용하여 전체 문제의 최적해를 구하는 DP의 구조, 특히 LCS와 같이 순서가 중요한 문제를 다룰 때 DP 테이블의 각 셀이 어떤 의미를 가지는지, 그리고 어떤 상태 전이를 통해 값을 갱신해야 하는지에 대한 명확한 이해를 얻었습니다. 또한, 1-indexed DP 테이블 사용의 이점과 문자열 인덱싱과의 관계를 명확히 할 수 있었습니다.