최장 공통 부분 수열 (Longest Common Subsequence)

정의

최장 공통 부분 수열 (Longest Common Subsequence, LCS) 은 두 수열 A, B 에서 순서를 유지하며 공통으로 등장하는 부분 수열 중 가장 긴 것을 찾는 문제.

예: A = ABCBDAB, B = BDCAB → LCS = BCAB, 길이 4.

부분 수열은 연속하지 않아도 됨 (부분 문자열과 다름). 유전자 염기서열 비교, diff 알고리즘, 텍스트 유사도 측정에 핵심.

문제 상황과 동기

길이 N, M 인 두 수열의 LCS 길이를 구한다.

• naive: 모든 부분집합 조합 2^N × 2^M. N, M > 20 불가.
• DP: O(NM) - 2차원 테이블로 점화식 해결.

핵심 통찰: A[i] 와 B[j] 가 같으면 둘 다 포함, 다르면 둘 중 하나 제외한 최대.

PS: 문자열 편집 거리, 버전 관리 (git diff), 생물정보학 (sequence alignment).

시각화

핵심 아이디어

dp[i][j] = A[0..i-1] 과 B[0..j-1] 의 LCS 길이.

점화식:

dp[i][j] = 
  if i == 0 or j == 0: 0
  elif A[i-1] == B[j-1]: dp[i-1][j-1] + 1
  else: max(dp[i-1][j], dp[i][j-1])

최종 답 = dp[N][M].

수열 복원 (Traceback)

dp 테이블을 역추적:

i = N, j = M
while i > 0 and j > 0:
  if A[i-1] == B[j-1]:
    result.push(A[i-1])
    i--, j--
  elif dp[i-1][j] > dp[i][j-1]:
    i--
  else:
    j--
reverse(result)

알고리즘

lcs(A, B):
    N = len(A), M = len(B)
    dp[0..N][0..M] = 0
    for i = 1..N:
        for j = 1..M:
            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])
    return dp[N][M]

구현

// LCS O(NM), traceback 포함
#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";
  // traceback
  string lcs;
  int i = n, j = m;
  while (i > 0 && j > 0) {
      if (a[i-1] == b[j-1]) {
          lcs.push_back(a[i-1]);
          i--; j--;
      } else if (dp[i-1][j] > dp[i][j-1]) i--;
      else j--;
  }
  reverse(lcs.begin(), lcs.end());
  cout << lcs << "\n";
}

# LCS O(NM), traceback 포함
import sys
input = sys.stdin.readline
​
a = input().strip()
b = input().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])
​
# traceback
lcs = []
i, j = n, m
while i > 0 and j > 0:
  if a[i-1] == b[j-1]:
      lcs.append(a[i-1])
      i -= 1
      j -= 1
  elif dp[i-1][j] > dp[i][j-1]:
      i -= 1
  else:
      j -= 1
print(''.join(reversed(lcs)))

// LCS O(NM), traceback 포함
import java.util.*;
import java.io.*;
public class Main {
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      String a = br.readLine();
      String b = br.readLine();
      int n = a.length(), m = b.length();
      int[][] dp = new int[n + 1][m + 1];
      
      for (int i = 1; i <= n; i++) {
          for (int j = 1; j <= m; j++) {
              if (a.charAt(i-1) == b.charAt(j-1))
                  dp[i][j] = dp[i-1][j-1] + 1;
              else
                  dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
          }
      }
      System.out.println(dp[n][m]);
      
      // traceback
      StringBuilder lcs = new StringBuilder();
      int i = n, j = m;
      while (i > 0 && j > 0) {
          if (a.charAt(i-1) == b.charAt(j-1)) {
              lcs.append(a.charAt(i-1));
              i--; j--;
          } else if (dp[i-1][j] > dp[i][j-1]) i--;
          else j--;
      }
      System.out.println(lcs.reverse());
  }
}

ABCBDAB
BDCAB

4
BCAB

AGGTAB
AGGTAB

6
AGGTAB

ABCD
EFGH

0

복잡도

변형 / 활용

공간 최적화 O(min(N, M))

현재 행만 유지. 단, traceback 불가.

vector<int> prev(m + 1, 0), curr(m + 1, 0);
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        if (a[i-1] == b[j-1])
            curr[j] = prev[j-1] + 1;
        else
            curr[j] = max(prev[j], curr[j-1]);
    }
    swap(prev, curr);
}
return prev[m];

Longest Common Substring (연속)

LCS 는 부분 수열 (연속 X). 부분 문자열 (substring) 은 다른 DP.

dp[i][j] = 
  if A[i-1] == B[j-1]: dp[i-1][j-1] + 1
  else: 0

Edit Distance (Levenshtein)

LCS 와 유사하나, 삽입 / 삭제 / 치환 비용 포함.

dp[i][j] = min(
  dp[i-1][j] + 1,      # delete
  dp[i][j-1] + 1,      # insert
  dp[i-1][j-1] + (A[i-1] != B[j-1])  # replace
)

3-way LCS

세 수열 A, B, C 의 LCS. O(NML) 3차원 DP.

dp[i][j][k] = 
  if A[i-1] == B[j-1] == C[k-1]: dp[i-1][j-1][k-1] + 1
  else: max(dp[i-1][j][k], dp[i][j-1][k], dp[i][j][k-1])

함정

1. 1-indexed vs 0-indexed

dp[i][j] 는 A[0..i-1], B[0..j-1] 의 LCS. 인덱스 헷갈림 주의.

2. 부분 수열 vs 부분 문자열

LCS 는 연속하지 않아도 됨. 연속 부분 문자열은 다른 문제 (Longest Common Substring).

3. traceback 방향

dp 테이블을 (N, M) 에서 역으로 (0, 0) 까지. 결과는 reverse 필요.

4. 공간 최적화시 traceback 불가

O(min(N, M)) 공간 최적화는 길이만 구할 수 있음. 수열 복원은 O(NM) 테이블 필요.

BOJ 연습 문제

참고

• 동적 계획법
• 최장 증가 부분 수열 (LIS)