Longest Common Subsequence (LCS)

개념

Longest Common Subsequence (최장 공통 부분 수열)
두 문자열에서 문자의 상대적인 순서를 유지하면서 공통으로 만들 수 있는 가장 긴 Subsequence (부분 수열)의 길이를 구한다.

• Subsequence (부분 수열): 일부 문자를 삭제할 수 있지만 순서는 변경할 수 없음
• 연속할 필요는 없음 → Substring (부분 문자열)과 차이
• 길이 n인 문자열은 총 2^n개의 부분 수열을 가짐

예:

s1 = "AGGTAB"
s2 = "GXTXAYB"

LCS = "GTAB"
length = 4

---

핵심 아이디어

두 문자열의 길이를 각각 m, n이라 하고 마지막 문자를 비교한다.

1. 마지막 문자가 같음

s1[m-1] == s2[n-1]

해당 문자는 LCS에 포함시킬 수 있으므로

LCS(m, n) = 1 + LCS(m-1, n-1)

2. 마지막 문자가 다름

둘 중 하나는 버려야 한다.

LCS(m, n)
= max(
    LCS(m-1, n),
    LCS(m, n-1)
)

Base Case (기저 조건)

둘 중 하나가 빈 문자열이면:

LCS(0, n) = 0
LCS(m, 0) = 0

이 Recurrence Relation (점화식)이 모든 풀이의 핵심이다.

---

Naive Recursion (단순 재귀)

점화식을 그대로 재귀로 구현한다.

문자가 다를 때마다

(m-1, n)
(m, n-1)

두 갈래로 분기한다.

같은 (m, n) 상태를 여러 번 계산하는 Overlapping Subproblems (중복 부분 문제)가 발생한다.

• Time: 지수 시간
• Space: 재귀 호출 스택 필요

따라서 입력이 커지면 비효율적이다.

---

Memoization / Top-Down DP (메모이제이션 / 하향식 DP)

재귀 결과 LCS(m, n)을 memo[m][n]에 저장한다.

이미 계산됨 → 바로 반환
아직 없음 → 계산 후 저장

가능한 상태는

0 <= i <= m
0 <= j <= n

이므로 최대 (m+1)(n+1)개.

• Time: O(mn)
• Space: O(mn) + 재귀 스택

핵심은 중복 계산 제거.

---

Bottom-Up DP / Tabulation (상향식 DP / 테이블화)

dp[i][j]를 다음과 같이 정의한다.

s1의 처음 i개 문자와 s2의 처음 j개 문자의 LCS 길이

초기값

dp[0][j] = 0
dp[i][0] = 0

빈 문자열과의 LCS는 항상 0.

Transition (상태 전이)

if s1[i-1] == s2[j-1]:
    dp[i][j] = dp[i-1][j-1] + 1
else:
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])

최종 답:

dp[m][n]

• Time: O(mn)
• Space: O(mn)

---

Space Optimized DP (공간 최적화 DP)

dp[i][j] 계산에 필요한 값은 사실 세 개뿐이다.

dp[i-1][j]     // 위
dp[i][j-1]     // 왼쪽
dp[i-1][j-1]   // 왼쪽 위

따라서 모든 행을 저장할 필요가 없다.

1차원 DP

dp[j]를 갱신하기 전:

dp	0		1		2		3		4		5	..
0		i-1,j-1	  i-1,j
1		i,	j-1    i,j
2
3
4
5

dp[j]   = 이전 행의 dp[i-1][j]
dp[j-1] = 현재 행의 dp[i][j-1]
prev    = 이전 행의 dp[i-1][j-1]

그러므로:

if match:
    dp[j] = prev + 1
else:
    dp[j] = max(dp[j], dp[j-1])

단, dp[j]를 덮어쓰기 전에 기존 값을 temp에 보관하고 다음 반복의 prev로 넘겨야 한다.

temp = dp[j]

현재 dp[j] 계산

prev = temp

• Time: O(mn)
• Space: O(n)
• 더 짧은 문자열을 DP 배열로 잡으면 O(min(m,n))

---

핵심 정리

dp[i][j]
= s1[0..i-1], s2[0..j-1]의 LCS 길이

같으면:
dp[i][j] = dp[i-1][j-1] + 1

다르면:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])

LCS는 대표적인 Dynamic Programming (동적 계획법) 문제이며,

2개의 문자열 Prefix (접두 구간)를 상태로 만들고, 마지막 문자의 일치 여부에 따라 상태를 줄인다.

라는 관점이 핵심이다.

복잡도

방법	Time	Space
Naive Recursion (단순 재귀)	Exponential	재귀 스택
Memoization (메모이제이션)	O(mn)	O(mn)
Bottom-Up DP (상향식 DP)	O(mn)	O(mn)
Space Optimized DP (공간 최적화)	O(mn)	O(min(m,n))

---

Applications (활용)

• Diff Utility (차이 비교 도구)
• 파일 간 공통 부분 및 변경 내용 탐색
• Version Control System (버전 관리 시스템)에서 변경 사항 비교 GeeksforGeeks