LCS(최장 공통 부분 수열 & 문자열 DP 문제)

문제 개요: “두 문자열에서 가장 긴 공통 부분 수열을 찾아라”

LCS(Longest Common Subsequence) 문제는,
두 문자열 A와 B가 주어졌을 때
"순서를 유지하면서 가장 긴 공통 부분 수열"의 길이를 구하는 문제입니다.

 주의: 부분 문자열(substring)이 아니라 부분 수열(subsequence)입니다.

 

예시:

A = "ACAYKP"
B = "CAPCAK"

→ LCS = "ACAK" → 길이 = 4

---

부분 수열 vs 부분 문자열 차이

항목부분	수열부분	문자열
정의	순서 유지, 중간 문자 건너뛰기 가능	연속된 문자의 부분
예	"ACAYKP" → "AYK", "AK" 가능	"ACAYKP" → "ACA"만 가능
문제 예시	LCS, 부분 집합 문제	슬라이딩 윈도우, 연속 최대합 등

---

핵심 사고 방식: DP 테이블로 두 문자열 비교

테이블 정의:

• dp[i][j]: A 문자열의 앞 i글자와 B 문자열의 앞 j글자에서의 LCS 길이

점화식 유도:

A[i-1] == B[j-1] → dp[i][j] = dp[i-1][j-1] + 1
A[i-1] != B[j-1] → dp[i][j] = max(dp[i-1][j], dp[i][j-1])

 

즉, 문자가 같다면 공통 수열에 포함
다르면 지금까지의 최장 수열 중 더 긴 쪽을 선택

 

---

시각적으로 점화식 이해하기

A: A  C  A  Y  K  P
B: C  A  P  C  A  K

       ↓ dp 테이블 초기화 예시
      0 0 0 0 0 0 0
    0
    0
    0
    0
    0
    0

 

• 두 문자열의 길이 + 1 만큼 2차원 배열 초기화
• 0행/0열은 "빈 문자열"과의 비교

---

Python 코드

def lcs(a, b):
    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])

    return dp[n][m]

 

 

만일 최장 공통 수열 자체를 출려하려면

단순히 길이만 구하는 게 아니라
LCS 문자열 자체를 복원하려면 역추적이 필요합니다.

 

def get_lcs(a, b):
    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])

    # 역추적
    i, j = n, m
    result = []
    while i > 0 and j > 0:
        if a[i - 1] == b[j - 1]:
            result.append(a[i - 1])
            i -= 1
            j -= 1
        elif dp[i - 1][j] >= dp[i][j - 1]:
            i -= 1
        else:
            j -= 1

    return ''.join(reversed(result))

---

시간/공간 복잡도

항목	복잡도
시간	O(n × m)
공간	O(n × m) (길이만 구한다면 O(min(n, m))도 가능)

• 문자열 길이가 작으면 그대로 쓰고,
  메모리 제한이 있을 경우 1D 배열 최적화도 가능

---

요약

 

• LCS는 순서를 유지하는 공통 수열 중 가장 긴 것을 찾는 문제
• 핵심은 2차원 DP 테이블 설계와
  “문자가 같으면 대각선 +1, 다르면 위/왼쪽 중 큰 값” 점화식
• 복원하려면 **역추적(backtracking)**을 추가해야 함
• Git, Bio, 에디터, 추천 시스템 등 실무 활용도 높음