[TIL] LCS 알고리즘 (최장 공통 부분 수열)

최장 공통 부분 수열(LCS, Longest Common Subsequence)

 - 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 수열

 

 

LIS 문제와 비슷한데 LCS는 수열 2개가 주어진다.

 

9251번: LCS (acmicpc.net)

9251번: LCS

위 문제를 예시로 들어 수열 ACAYKP와 CAPCAK를 가지고 표를 만들어 보았다.

이 때, 두 가지 경우를 고려해야 하는데

1. 같은 알파벳인 경우

2. 알파벳이 다른 경우

이다.

 

1번의 경우는 

ACA, CA 

ACAYKP, CAP

두 가지 부분을 살펴보면

같은 알파벳을 만날 경우 글자를 추가하기 전의 LCS 값에 +1을 하는 규칙이 있다.

즉, [i-1][j-1]의 위치의 값에서 1을 더한 값이다.

 

2번의 경우는

AC, CAPCA

이 부분을 살펴볼 때,

두 가지 상황을 고려할 수 있다.

1) AC, CAPC를 비교

2) A, CAPCA를 비교

 

1)의 경우 LCS 는 2이고,  2)의 경우 LCS는 1이다.

 

따라서 AC와 CAPCA 즉, C와 A가 만나는 위치의 값은 위의 두 가지 경우 중 최대값을 구하여 넣으면 된다. 

 

이를 고려하여 코드를 짠다면 다음과 같이 짤 수 있다.

 

import sys
input = sys.stdin.readline

lst1 = [*map(str, input().strip())]
lst2 = [*map(str, input().strip())]

dp=[[0]* (len(lst2)+1) for _ in range(len(lst1)+1)]


for i in range(1, len(lst1)+1):
    for j in range(1, len(lst2)+1):
        if lst1[i-1] == lst2[j-1]:
            dp[i][j] = dp[i-1][j-1]+1
        else:
            dp[i][j] = max(dp[i][j-1], dp[i-1][j])
            

print(dp[-1][-1])

 

dp리스트는 각 문자열의 길이만큼을 가지는 이차원 배열로 

이중 for문을 돌며 위의 로직대로 알고리즘을 짜 준다.

그럼 이차원 배열의 마지막 부분이 두 문자열의 LCS 값이 되므로 출력해주면 된다.