LCS (Longest Common Subsequence) — 점화식을 손으로 납득하기까지

DP 문제를 풀 때 점화식을 외우는 건 별로 좋아하지 않는다. 어차피 까먹는다. 그래서 LCS도 직접 납득하고 싶었다.

LCS가 뭔지부터

두 수열이 주어졌을 때, 양쪽에 공통으로 존재하는 부분 수열 중 가장 긴 것.
연속일 필요는 없고, 순서만 유지하면 된다.

A = "ABCDE"
B = "ACE"
→ LCS = "ACE" (길이 3)

dp 테이블 정의

dp[i][j] = A의 i번째, B의 j번째까지 고려했을 때의 LCS 길이

여기까지는 자연스럽게 나왔다.

종이에 매트릭스를 그리면서 막혔던 부분

2차원 테이블을 채우는 게 LCS의 전형적인 풀이라는 건 알고 있었다. 그래서 직접 그려봤는데, 두 가지가 와닿지 않았다.

첫째, A[i] == B[j]일 때 왼쪽 대각선 위 dp[i-1][j-1]에서 값을 가져온다는 게 기계적으로만 보였다. 왜 하필 대각선인지.

둘째, A[i] != B[j]일 때 왼쪽과 위 중 max를 취하는데, 대각선은 왜 고려 안 해도 되는지. 매트릭스를 채우다 보니 자연스럽게 드는 의문이었다.

납득한 과정

Case 1: `A[i] == B[j]`

두 문자가 같다면, 이걸 LCS의 마지막 문자로 쓰기로 결정한다.
그러면 나머지 LCS는 A의 i-1번째까지, B의 j-1번째까지에서 와야 한다.
두 문자를 둘 다 소비했으니까.

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

매트릭스에서 대각선 왼쪽 위로 보이는 건 이 정의의 시각화일 뿐이었다. 정의로 생각하니 바로 납득됐다.

Case 2: `A[i] != B[j]`

두 문자가 다르면 둘 중 하나를 없는 사람 취급한다.
LCS니까 더 긴 쪽을 선택한다.

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

추가로 든 의문: 왜 대각선(`dp[i-1][j-1]`)은 max에 포함 안 해도 되나?

Case 2에서 max(dp[i-1][j], dp[i][j-1])를 쓰는데, 대각선인 dp[i-1][j-1]도 고려해야 하지 않냐는 의문이 생겼다.

결론은 필요 없다.

dp[i-1][j-1] <= dp[i-1][j] 이고 dp[i-1][j-1] <= dp[i][j-1] 가 항상 성립한다.
한 칸 더 고려할수록 LCS는 같거나 늘어날 수는 있어도 줄지 않기 때문에, 대각선은 max에서 어차피 선택되지 않는다.

구현

경계 처리를 위해 dp 테이블을 (n+1) x (m+1)로 잡고, 0번째 행/열을 0으로 초기화한다.
A와 B의 인덱스는 1-based dp 인덱스에서 -1 오프셋으로 접근한다.

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

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

    vector<vector<int>> dp(A.size() + 1, vector<int>(B.size() + 1));

    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] = max(dp[i-1][j], dp[i][j-1]);
            else
                dp[i][j] = dp[i-1][j-1] + 1;
        }
    }

    cout << dp[A.size()][B.size()];
    return 0;
}

답은 dp[A.size()][B.size()].

정리

외우려고 하면 헷갈린다. dp[i][j]의 정의를 정확히 붙잡고, 각 케이스에서 "무엇을 소비했는가"를 생각하면 점화식은 자연스럽게 따라온다.