[Algorithm] LCS (Longest Common Subsequence)

0. 문제

link: https://www.codetree.ai/missions/6/concepts/35/problems/dp-lcs-2/introduction

코드트리

LCS (Longest Common Subsequence) 란 최장 공통 부분 수열이다. 부분 수열이란 문자열 내에서 순서대로 뽑아서 나올 수 있는 수열을 의미한다. 그 중 두 문자열에게 공통으로 부분 수열인 경우 공통 부분 수열이라고 하며, 이 중 길이가 가장 긴 경우를 최장 공통 부분 수열이라고 한다. 예를 들면 ABABA와 BAAB의 LCS는 BAB이다. 

 

여기서 구하고자 하는 것은 문자열 A와 문자열 B가 주어졌을 때, LCS의 길이를 구하는 것이다.

 

1. 풀이

 

우선 문자열의 모든 부분을 검사해야 한다는 느낌은 올 것이다. 그러나 어떻게 하면 효율적으로 검사할 수 있을까?

이를 위해 우리는 동적계획법을 이용한다. 동적계획법의 핵심은 문제를 쪼개는 것이고, 여기에서는 dp[i][j]를 문자열 A의 i번째, 문자열 j번째까지 검사했을 때 최장 부분 수열의 길이를 구하는 것으로 하겠다. 

 

나의 동적계획법은 항상 나를 선택하느냐 선택하지 않느냐 를 기준으로 시작한다. 따라서 dp[i][j]는 문자열 A에서 i번째를, 문자열 B에서 j번째를 선택할 경우와 선택하지 않을 경우의 최소가 될 것이다. A의 i번째를 a, B의 j번째를 b라고 하겠다. 

 

a와 b가 같다면 고민의 여지없이 선택해야 할 것이다. 따라서 이때는 A의 i-1번째, B의 j-1번째까지를 고려했을때의 문자열에 a(==b)만 추가해주면 된다. 이 때 점화식은 다음과 같다.

 

dp[i][j] = dp[i-1][j-1] + 1

 

그러나 만약 a와 b가 다르다면, a를 선택할 지, b를 선택할 지 결정한 후 같은 문자가 나올 때까지 넘어가야 할 것이다. 

a를 선택하는 경우는 dp[i-1][j], b를 선택하는 경우는 dp[i][j-1]이 될 것이다. 따라서 점화식은 다음과 같다. 

 

dp[i][j] = max(dp[i-1][j], dp[i][j-1])

 

2. 구현

 

str1 = list(input())
str2 = list(input())

n1 = len(str1)
n2 = len(str2)

dp = [[0 for _ in range(n2)] for _ in range(n1)]

for i in range(n2):
    if str1[0] == str2[i]:
        dp[0][i:] = [1] * (n2 - i)
        break
for j in range(n1):
    if str2[0] == str1[j]:
        for k in range(j, n1):
            dp[k][0] = 1
        break

for i in range(1, n1):
    for j in range(1, n2):
        if str1[i] == str2[j]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])

for i in range(n1):
    print(dp[i])

A의 0번째와 같은 문자가 B에 있는지 검사하고, 있다면 그것을 선택하는 것이 A의 0번째 입장에선 최적이므로 나머지 배열을 모두 1로 채운다. B에도 동일한 과정을 거친다. 나머지는 선택하지 않는 경우 문자열의 길이가 0이므로 모두 0으로 초기화한다.