#알고리즘

LCS

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

1. 기본 개념

• 부분 수열 (Subsequence)
  원래 순서를 유지하지만, 중간의 몇 문자를 건너뛰어도 된다.
  예: ABCDEF에서 ACE는 부분 수열이다.

• 부분 문자열 (Substring)
  반드시 연속된 구간이어야 한다.
  예: ABCDEF에서 CDE는 부분 문자열이다.

즉, 부분 문자열은 부분 수열의 특수한 경우라고 볼 수 있다.

2. LCS (Longest Common Subsequence)

LCS란?
두 문자열이 있을 때, 공통된 부분 수열 중 가장 긴 것을 찾는 문제다.

예제:

• 문자열 1: ABCBDAB
• 문자열 2: BDCABA

가능한 LCS의 예시는 다음과 같다:

• BCBA (길이 4)
• BDAB (길이 4)

LCS는 유일하지 않을 수 있다.
그래서 보통은 길이만 구하는 것이 기본 문제이고, 실제 수열을 복원하는 것은 추가 과정이다.

3. 왜 단순 비교로는 어려운가?

문자열 길이가 n일 때, 각 문자를 고른다 / 안 고른다 두 가지 선택지가 있다.
→ 부분 수열의 개수는 $2^{n}$.

두 문자열 길이가 n, m이라면 가능한 모든 부분 수열 조합은 대략

가지가 된다.

즉, 단순 비교로는 지수 시간이 걸리므로 비효율적이다.
따라서 동적 계획법(DP)으로 시간 복잡도를 $O(nm)$까지 줄인다.

4. LCS DP 아이디어

핵심은 작은 문제(접두사)로 분해하기이다.

보통은 문자열 X, Y에 대해 다음과 같이 정의한다:

LCS(i, j) = 문자열 X의 앞에서 i개, 문자열 Y의 앞에서 j개를 고려했을 때 최장 공통 부분 수열의 길이

5. 점화식 세우기

1. 마지막 문자가 같을 때

   • 공통 부분 수열에 포함될 수 있음
     $LCS(i, j) = LCS(i-1, j-1) + 1$

2. 마지막 문자가 다를 때

   • 두 경우 중 더 긴 것을 선택
     $LCS(i, j) = \max(LCS(i-1, j), \; LCS(i, j-1))$

6. 기저 조건

• 한쪽 문자열이 공집합일 때 LCS 길이는 0이다.
  $LCS(0, j) = 0 \quad,\quad LCS(i, 0) = 0$

7. 최종 정리 (점화식)

8. 요약

• 부분 수열: 순서만 유지, 연속성 불필요
• 부분 문자열: 반드시 연속
• LCS 문제: 두 문자열의 공통된 부분 수열 중 최장 길이
• 해결 방법: DP로 (O(nm)) 시간에 해결 가능
• 실제 수열 복원: DP 테이블을 역추적(backtracking)해서 구한다