최장 공통 부분 수열

문제 정의

두 문자열(수열) \(A, B\)가 주어질 때, 둘 모두의 부분 수열(순서 유지, 연속일
필요 없음)이 되는 가장 긴 수열의 길이를 구합니다. 예: ACAYKP 와 CAPCAK
의 LCS는 ACAK (길이 4).

상태 정의

$$ dp[i][j] = A[1..i],\ B[1..j]\text{의 LCS 길이} $$

점화식

마지막 문자를 비교하면 두 경우뿐입니다.

$$ dp[i][j] = \begin{cases} dp[i-1][j-1] + 1 & A_i = B_j \\ \max(dp[i-1][j],\ dp[i][j-1]) & A_i \ne B_j \end{cases} $$

• 마지막 문자가 같으면 — 그 문자를 LCS에 포함시키는 것이 항상 손해가 아님을
  교환 논법으로 보일 수 있습니다.
• 다르면 — 둘 중 하나는 LCS에 못 들어가므로, 한쪽을 한 글자 줄인 두 경우의
  최댓값.

복잡도

상태 \(O(NM)\)개, 전이 \(O(1)\) → 시간·공간 \(O(NM)\). 길이만 필요하면 직전 행만
들고 있으면 되므로 공간을 \(O(M)\)으로 줄일 수 있습니다.

LIS와의 관계

• LCS는 두 수열의 공통 구조, LIS는 한 수열의 증가 구조.
• \(A\)와 "\(A\)를 정렬한 것"의 LCS = \(A\)의 LIS — 두 문제가 서로 환원됩니다.
• 두 수열 중 하나에 중복 원소가 없으면, LCS를 LIS로 바꿔 \(O(N \log N)\)에
  풀 수도 있습니다 (위치 치환 트릭).

전형적인 변형

길이 계산 (C++)

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

int main() {
    string a, b;
    cin >> a >> b;
    int n = a.size(), m = b.size();
    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++) {
            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[n][m] << '\n';
}

실제 LCS 복원

테이블을 \((n, m)\)에서 거꾸로 걸어 내려옵니다.

string s;
int i = n, j = m;
while (i > 0 && j > 0) {
    if (a[i-1] == b[j-1]) { s += a[i-1]; i--; j--; }      // LCS에 포함
    else if (dp[i-1][j] >= dp[i][j-1]) i--;               // 위로
    else j--;                                             // 왼쪽으로
}
reverse(s.begin(), s.end());

Python 구현

import sys

a = sys.stdin.readline().strip()
b = sys.stdin.readline().strip()
n, m = len(a), len(b)
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in range(1, m + 1):
        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])
print(dp[n][m])

파이썬은 \(N, M\)이 수천이면 이중 루프가 느립니다 — PyPy를 쓰거나, 행 단위로
리스트 컴프리헨션/비트셋 최적화를 고려하세요.

자주 하는 실수

• 인덱스 오프바이원 — dp[i][j]가 "앞 \(i\)글자 / 앞 \(j\)글자"임을 일관되게.
  문자 비교는 a[i-1] == b[j-1].
• 복원 시 dp[i-1][j] >= dp[i][j-1]의 등호 방향에 따라 (여러 답 중) 어떤
  LCS가 나오는지가 달라집니다 — 사전순 조건이 붙은 문제는 따로 처리.
• 공간 절약(1차원) 버전에서는 복원이 안 됩니다. 복원 문제면 2차원 유지.

연습 포인트

LCS 길이 → LCS 복원 → 편집 거리 → "공통 부분 문자열"(연속) 순서로 풀면
2차원 DP 설계가 손에 붙습니다.

출제 신호

• 문자열(수열) 두 개가 주어지고, "공통으로 나타나는 부분 수열의
  최대 길이"를 묻습니다. "부분 수열"은 건너뛰어도 되고, "부분 문자열(연속)"과는
  다른 문제임을 항상 먼저 구분하세요.
• "두 파일의 공통 부분", "편집 거리", "한 문자열을 다른 문자열로 만드는 최소
  연산" — LCS와 같은 2차원 DP 가족입니다.
• 제약 신호: 두 길이가 각각 \(\le 1000{\sim}3000\)이면 \(O(NM)\) 표 채우기입니다.
  길이가 \(10^5\)를 넘으면 평범한 LCS가 아니라 특수 조건(문자 종류 제한,
  한쪽이 순열 → LIS로 환원)이 숨어 있습니다.

특히 두 수열이 모두 순열(중복 없는 같은 원소 집합)이면, 한쪽 기준으로
번호를 매겨 다른 쪽을 수열로 바꾼 뒤 LIS로 \(O(N \log N)\)에 풉니다.
이 환원은 단골 출제 포인트입니다.

풀이 결정 절차

1. 연속이어야 하는가? — 연속(부분 문자열)이면 점화식이 다릅니다
   (같을 때만 dp[i-1][j-1]+1, 다르면 0).
2. \(N \times M\)이 \(10^7\) 안쪽인지 검산합니다. 메모리도 \(N \times M\) —
   int 4바이트 기준 3000\(\times\)3000은 36MB로 아슬아슬하니 자료형을 줄이거나
   두 행만 유지하는 최적화를 준비합니다.
3. 길이만 필요한가, 실제 수열 복원도 필요한가? 복원이 필요하면 표 전체를
   유지해야 하므로 두-행 최적화를 쓸 수 없습니다.

자주 하는 실수

• 인덱스 기준 혼란 — 1-based DP에 0-based 문자열을 섞으면 off-by-one이
  납니다. "dp[i][j] = A의 앞 \(i\)글자와 B의 앞 \(j\)글자의 LCS"로 정의하고,
  문자 비교는 A[i-1] == B[j-1]로 통일하는 게 가장 사고가 적습니다.

dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in range(1, m + 1):
        if A[i - 1] == B[j - 1]:               # i, j 는 "앞 몇 글자"
            dp[i][j] = dp[i - 1][j - 1] + 1
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

• 같을 때 max에 dp[i-1][j-1]+1만 넣지 않고 세 항을 전부 비교 — 답은
  같게 나오지만, 변형(가중 LCS 등)에서 점화식 이해가 흔들리는 원인이 됩니다.
  "같으면 대각선+1, 다르면 좌/상 중 최댓값"으로 의미를 기억하세요.
• 복원 방향 실수 — 복원은 dp[n][m]에서 거꾸로 내려옵니다. 문자가
  같으면 대각선으로 이동하며 그 문자를 채택하고, 아니면 값이 큰 쪽(좌/상)으로
  이동합니다. 모은 문자열을 마지막에 뒤집는 것을 잊는 실수가 많습니다.
• 부분 문자열 문제에 LCS 점화식 사용 — "연속"이라는 단어 하나로 문제가
  바뀝니다. 읽기 단계에서 표시해 두세요.

연습 방법

사이드바 연습 목록에서 길이만 묻는 기본 LCS → 복원까지 요구하는 문제 →
편집 거리 → 순열 LCS(LIS 환원) 순서로 푸는 것을 권합니다. 표를 채우는 문제는
작은 예제(길이 4~5)를 손으로 표를 그려 점화식을 검증하는 습관이 디버깅
시간을 크게 줄여 줍니다. 태그된 문제 3문제 이상 해결 시 마스터 처리되어
레이팅 CLASS 보너스에 반영됩니다.