[DP] 최장 공통 부분 수열(LCS; Longest Common Subsequence)

최장 공통 부분 수열이란?

최장 공통 부분 수열이란 두 수열이 주어졌을 때, 둘 모두의 부분 수열이 되는 수열 중 가장 긴 것을 의미한다.

 

예를 들어,

MANGOJUICE

AGODATRIP

위 두 문자열의 LCS는 AGOI이다.

 

LCS 길이 구하기

LCS는 DP를 이용해 구할 수 있다.

두 수열 $a_n, b_n$이 있을 때, $a_n$의 $i$번째 원소와 $b_n$의 $j$번째 원소까지 봤을 때의 최장 공통 부분 수열의 길이를 $dp[i][j]$라고 하자.

 

아래와 같은 점화식을 세울 수 있다.

• $i = 0$ 또는 $j = 0$일 때, $dp[i][j] = 0$
• $a_i = b_j$일 때, $dp[i][j] = dp[i - 1][j - 1] + 1$
• $a_i \neq b_j$일 때, $dp[i][j] = MAX(dp[i - 1][j], dp[i][j - 1])$

 

시간 복잡도는 $O(|a_n||b_n|)$이 된다.

 

코드(Python)

la, lb = len(ai), len(bj)
dp = [[0] * (lb + 1) for _ in range(la + 1)]

for i, ai in enumerate(a):
    for j, bj in enumerate(b):
        if ai == bj:
            dp[i + 1][j + 1] = dp[i][j] + 1
        else:
            dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j])

print(dp[la][lb])