최장 공통 부분수열(LCS) 과 DP 역추적

백준 17218 비밀번호 만들기
=> 최장 공통 부분수열(LCS) 과 DP 역추적

두 개의 문자열 s1과 s2가 주어졌을 때, 이 두 문자열이 공통으로 갖는 부분수열(subsequence) 중 길이가 가장 긴 것을 구하는 문제이다. 부분수열은 원래 문자열에서 문자를 삭제해 얻을 수 있는 순서를 유지하는 문자열을 말한다. 예를 들어 “ABCBDAB”의 부분수열로 “BCBA”가 있다.

동적 계획법(DP) 점화식

크기가 (n+1)×(m+1)인 2차원 배열 dp를 정의한다.
dp[i][j]는 s1의 처음 i글자(s1[0..i‑1])와
s2의 처음 j글자(s2[0..j‑1])로 만들 수 있는
최장 공통 부분수열(LCS)의 길이를 의미한다.

$$
dp[i][j] =
\begin{cases}
dp[i-1][j-1] + 1, & \text{if } s1[i-1] = s2[j-1],\\
\max\bigl(dp[i-1][j],\,dp[i][j-1]\bigr), & \text{otherwise}.
\end{cases}
$$

세부 설명

• 문자 일치 시
  s1[i-1] = s2[j-1] 이면 이전 단계 dp[i-1][j-1]에
  지금 일치한 문자를 추가하므로 dp[i][j] = dp[i-1][j-1] + 1 이다.
  예: s1="ABC", s2="XBC"
  'C'가 일치하므로, dp[3][3] = dp[2][2] + 1 = 2 + 1 = 3
• 문자 불일치 시
  s1[i-1] ≠ s2[j-1] 이면
  한쪽 문자열의 마지막 문자를 버리는 두 가지 경우를 고려한다:
  dp[i-1][j] (s1 끝 문자 버림) 또는
  dp[i][j-1] (s2 끝 문자 버림)
  그 중 더 큰 값을 취한다.
  수식: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
  예: s1="AB", s2="AC"
  'B' vs 'C' 불일치 →max(dp[1][2], dp[2][1]) = max(1,1) = 1

초기화

• dp[0][j] = 0 (빈 문자열 vs s2[:j])
• dp[i][0] = 0 (s1[:i] vs 빈 문자열)

코드 전체

# 바이트 단위로 두 문자열 읽기
s1, s2 = open(0, 'rb').read().split()
n, m = len(s1), len(s2)

# dp 테이블 초기화
dp = [[0] * (m + 1) for _ in range(n + 1)]

# 1) LCS 길이 계산
for i in range(1, n + 1):
    for j in range(1, m + 1):
        if s1[i-1] == s2[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = dp[i-1][j] if dp[i-1][j] >= dp[i][j-1] else dp[i][j-1]

# 2) 역추적으로 부분수열 복원
res = bytearray()
i, j = n, m
while i > 0 and j > 0:
    if s1[i-1] == s2[j-1]:
        res.append(s1[i-1])
        i -= 1
        j -= 1
    else:
        if dp[i-1][j] >= dp[i][j-1]:
            i -= 1
        else:
            j -= 1

res.reverse()
open(1, 'wb').write(res)

예시: s1 = "ABCBDAB", s2 = "BDCABA"

DP 테이블 채우기

dp 테이블을 채우는 핵심은 i = 1..n, j = 1..m 이중 반복문을 돌며 각 위치의 최적 해를 구하는 것입니다.

1) 반복 구조

for i in range(1, n+1):
    for j in range(1, m+1):
        … 상태 갱신 …

2) 상태 갱신(state transition)

• 문자 일치 (s1[i-1] == s2[j-1])  dp[i][j] = dp[i-1][j-1] + 1
• 문자 불일치 (s1[i-1] != s2[j-1])  dp[i][j] = max(dp[i-1][j], dp[i][j-1])

3) 예시 단계(i=1, j=4)
상황: s1[0] = 'A', s2[3] = 'A' → 일치하므로
dp[1][4] = dp[0][3] + 1 = 0 + 1 = 1

4) 예시 단계(i=2, j=2)
상황: s1[1] = 'B', s2[1] = 'D' → 불일치이므로
dp[2][2] = max(dp[1][2], dp[2][1]) = max(0, 1) = 1

5) 전체 흐름 요약

• 행 i=1부터 시작해, 각 열 j=1..m을 순회
• 두 문자를 비교해 일치 → 대각선+1, 불일치 → 위·왼쪽 중 최대

이 과정을 모두 마치면, dp[n][m]에 LCS 길이가 채워짐

아래 표는 s1의 각 문자(세로축, i)와 s2의 각 문자(가로축, j)에 대해 dp[i][j]를 채운 모습이다. 표의 가장 오른쪽 아래(dp[7][6]) 값 4가 두 문자열의 LCS 길이다.

i＼j	0 (j=0)	B (j=1)	D (j=2)	C (j=3)	A (j=4)	B (j=5)	A (j=6)
0 (i=0)	0	0	0	0	0	0	0
A (i=1)	0	0	0	0	1	1	1
B (i=2)	0	1	1	1	1	2	2
C (i=3)	0	1	1	2	2	2	2
B (i=4)	0	1	1	2	2	3	3
D (i=5)	0	1	2	2	2	3	3
A (i=6)	0	1	2	2	3	3	4
B (i=7)	0	1	2	2	3	4	4

• 첫 행(i=0)과 첫 열(j=0)은 빈 문자열과의 비교이므로 모두 0으로 초기화한다.
• 예를 들어 dp[6][5] = 3은 s1[:6] = "ABCBDA"와 s2[:5] = "BDCAB"의 LCS 길이가 3임을 뜻한다.

역추적(backtracking) 과정

표의 맨 오른쪽 아래(i=7, j=6)에서 시작해, 아래 규칙에 따라 한 칸씩 이동하며 실제 LCS를 복원한다.

1. 시작: 위치 (i=7, j=6), 값 = dp[7][6] = 4. 두 문자가 불일치하면 위 또는 왼쪽 칸 중 큰 쪽으로 이동.
2. 비교: s1[6] = 'B', s2[5] = 'A' → 불일치 위쪽 dp[6][6] = 4, 왼쪽 dp[7][5] = 4 중 값이 같으므로 i = 6 (위쪽)으로 이동.
3. (6,6): s1[5] = 'A', s2[5] = 'A' → 일치 결과에 'A' 추가 → 이동 (i=5, j=5).
4. (5,5): s1[4] = 'D', s2[4] = 'B' → 불일치 위쪽 dp[4][5] = 3 ≥ 왼쪽 dp[5][4] = 2 → 이동 (i=4, j=5).
5. (4,5): s1[3] = 'B', s2[4] = 'B' → 일치 결과에 'B' 추가 → 이동 (i=3, j=4).
6. (3,4): s1[2] = 'C', s2[3] = 'A' → 불일치 위쪽 dp[2][4] = 1 < 왼쪽 dp[3][3] = 2 → 이동 (i=3, j=3).
7. (3,3): s1[2] = 'C', s2[2] = 'C' → 일치 결과에 'C' 추가 → 이동 (i=2, j=2).
8. (2,2): s1[1] = 'B', s2[1] = 'D' → 불일치 위쪽 dp[1][2] = 0 < 왼쪽 dp[2][1] = 1 → 이동 (i=2, j=1).
9. (2,1): s1[1] = 'B', s2[0] = 'B' → 일치 결과에 'B' 추가 → 이동 (i=1, j=0) → 종료.

결과 문자열 완성

순서대로 추가된 문자: A → B → C → B → 뒤집으면

BCBA

얘들아 거기 아니야...