LCS (Longest Common Subsequence): 두 시퀀스의 유사도 측정

1. 문제 정의

두 시퀀스 $X$와 $Y$의 최장 공통 부분 수열을 찾는 문제다. diff 도구나 생물정보학(DNA 비교) 등에서 핵심적으로 쓰인다.

---

2. 점화식 (Recurrence Relation)

\[c[i, j] = \begin{cases} 0 & \text{if } i=0 \text{ or } j=0 \\ c[i-1, j-1] + 1 & \text{if } x_i = y_j \\ \max(c[i, j-1], c[i-1, j]) & \text{if } x_i \neq y_j \end{cases}\]

• 문자가 같으면: 대각선 위 값 + 1 (공통 수열 연장)
• 문자가 다르면: 왼쪽이나 위쪽 중 큰 값 (기존 최댓값 유지)

---

3. 공간 복잡도 최적화 (Sliding Window)

기본 DP는 $O(MN)$ 메모리를 쓴다. 하지만 점화식을 보면 바로 윗 행(Previous Row)만 있으면 현재 행을 계산할 수 있다. 따라서 $2 \times \min(M, N)$ 메모리만으로도 LCS의 길이는 구할 수 있다. (단, 역추적을 하려면 Hirschberg 알고리즘 등의 추가 기법이 필요하다.)