역추적 (DP Traceback)

정의

역추적 (Traceback) 은 DP 표를 채울 때 parent / choice 배열에 최적해의 결정을 기록하고, 최종 상태에서 출발하여 거꾸로 따라가며 최적해를 복원하는 기법.

문제 상황과 동기

DP 는 보통 최적해의 값 (최댓값/최솟값) 만 반환. 하지만 LCS 의 실제 문자열, Knapsack 에서 넣은 물건 목록, LIS 의 실제 수열 등 구체적인 해가 필요할 때가 많음.

핵심 통찰: DP 점화식에서 각 상태가 어디서 왔는지 (점화식의 선택지 중 어느 branch) 를 기록해 두면, 마지막 상태에서 역방향으로 따라가며 재구성 가능.

시각화

핵심 아이디어

invariant: parent[i][j] 는 dp[i][j] 가 어떤 이전 상태에서 왔는지 기록.

LCS 점화식:
  if a[i] == b[j]:
    dp[i][j] = dp[i-1][j-1] + 1
    parent[i][j] = DIAG (대각선)
  else:
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    if dp[i-1][j] >= dp[i][j-1]:
      parent[i][j] = UP (위)
    else:
      parent[i][j] = LEFT (왼쪽)

Traceback (LCS 예):
  i = n, j = m
  while i > 0 and j > 0:
    if parent[i][j] == DIAG:
      answer.push(a[i-1])
      i--, j--
    elif parent[i][j] == UP:
      i--
    else:
      j--
  reverse(answer)

알고리즘

DP_TABLE(dp, choice, input)

TRACEBACK(choice, final_state):
    path = []
    state = final_state
    while state != initial_state:
        decision = choice[state]
        if decision == CHOICE_A:
            record step А
            state = prev_A(state)
        elif decision == CHOICE_B:
            record step Б
            state = prev_B(state)
        ...
    reverse(path)
    return path

구현

// LCS with traceback. parent[]: 0=UP, 1=LEFT, 2=DIAG
#include <bits/stdc++.h>
using namespace std;
​
int main() {
  string a, b;
  cin >> a >> b;
  int n = a.size(), m = b.size();
​
  vector dp(n + 1, vector<int>(m + 1, 0));
  vector par(n + 1, vector<int>(m + 1, 0));
  // 0: UP, 1: LEFT, 2: DIAG
​
  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;
              par[i][j] = 2;
          } else if (dp[i - 1][j] > dp[i][j - 1]) {
              dp[i][j] = dp[i - 1][j];
              par[i][j] = 0;
          } else {
              dp[i][j] = dp[i][j - 1];
              par[i][j] = 1;
          }
      }
  }
​
  // Traceback: follow parent from (n, m) to (0, 0)
  string lcs;
  int i = n, j = m;
  while (i > 0 && j > 0) {
      if (par[i][j] == 2) {       // DIAG: matched char
          lcs.push_back(a[i - 1]);
          i--; j--;
      } else if (par[i][j] == 0) {// UP
          i--;
      } else {                    // LEFT
          j--;
      }
  }
  reverse(lcs.begin(), lcs.end());
​
  cout << dp[n][m] << "\n" << lcs << "\n";
  return 0;
}

# LCS with traceback
a = input().strip()
b = input().strip()
n, m = len(a), len(b)
​
dp = [[0] * (m + 1) for _ in range(n + 1)]
par = [[0] * (m + 1) for _ in range(n + 1)]
# 0: UP, 1: LEFT, 2: DIAG
​
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
          par[i][j] = 2
      elif dp[i - 1][j] > dp[i][j - 1]:
          dp[i][j] = dp[i - 1][j]
          par[i][j] = 0
      else:
          dp[i][j] = dp[i][j - 1]
          par[i][j] = 1
​
# Traceback
lcs = []
i, j = n, m
while i > 0 and j > 0:
  if par[i][j] == 2:
      lcs.append(a[i - 1])
      i -= 1; j -= 1
  elif par[i][j] == 0:
      i -= 1
  else:
      j -= 1
​
lcs.reverse()
print(dp[n][m])
print("".join(lcs))

ABCBDAB
BDCABA

4
BCAB

ABC
DEF

0

복잡도

변형 / 활용

함정

1. parent 공간

parent 배열은 DP table 과 같은 크기. DP 크기가 10^6 이상이면 메모리 부담. 경로만 필요한 경우 reconstruction 은 BFS parent tree 처럼 배열 하나로도 가능.

2. 역순 복원 후 reverse

Traceback 은 끝에서 시작 → 시작에서 끝 순서로 복원하려면 반드시 reverse 필요. 깜빡하면 역순 결과 출력.

3. 부모 선택이 모호할 때

dp 값이 같은 여러 부모 중 하나를 고르면 다른 결과. “아무 LCS 나 좋다” vs “사전순/최소” 요구 사항 확인.

BOJ 연습 문제

참고

• LCS (최장 공통 부분 수열)
• 배낭 문제
• LIS (최장 증가 부분 수열)