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

LCS (Longest Common Subsequence)이란?

2개 이상의 문자열에서에서 공통으로 나타나는 부분 문자열 중 가장 긴 문자열을 의미합니다.

LCS은 대표적으로 DNA의 공통 염기서열을 찾아 데이터를 압축하거나 무선 서명을 통해 휴대폰에서 사용자를 인증할 때 사용됩니다.

 

LCS 예시

두 문자열 X, Y가 다음과 같이 주어질 때 LCS(X, Y)는 다음과 같습니다.

X: ACAYKP,  Y: CAPCAK 

LCS(X, Y) = 4

 

1. Top-down 방법 (재귀적 풀이)

문자열 X, Y가 X = [x1, x2, x3, x4, .... , xm], Y = [y1, y2, y3, .... , yn] 일 때, LCS의 Top-down 방법은 다음과 같은 과정을 반복합니다.

 

이를 슈도코드는 다음과 같습니다.

LCS(X, Y): #수열 X와 Y의 최장 공통 부분 수열(LCS)의 길이
    m, n = len(X), len(Y)
    if m == 0 or n == 0:
        return 0
    else:
    	if X[-1] == Y[-1]:
            return LCS(X[:m-1], Y[:n-1]) + 1
        else:
            return max(LCS(X, Y[:n-1]), LCS(X[:m=-1], Y))

 

LCS에서의 중복 부분 문제

LCS에서 하나의 값을 여러 번 호출하기 때문에 중복되는 부분 문제가 발생합니다.

그래서 재귀적으로 LCS를 해결할 경우 O(2^n)이라는 시간복잡도를 가지게 됩니다.

 

2. Bottom-up 방법 (동적계획법 풀이)

Top-down 방식과 반대로 하여 중복 부분 문제는 한번만 계산하도록 바꿔 시간복잡도를 낮췄습니다.

 

DP 테이블을 이용하여 미리 계산한 값을 저장합니다.

DP테이블을 저장하는 방법은 같은 문자가 나오면 왼쪽 대각선 값에 1을 더해준 값을 넣어줍니다.

다를 경우 위쪽이나 왼쪽 값 중 더 큰 값을 저장합니다.

이렇게 DP 테이블을 채우는 이유는 재귀적 풀이를 이해하면 금방 이해할 수 있습니다.

두 문자열이 X = CBDA, Y = ACADB라고 하면 DP 테이블은 다음과 같이 채워질 수 있습니다.

위 두 문자열의 LCS는 DP[5][4] = 2 입니다.

 

Bottom-up 방식의 슈도코드는 다음과 같습니다.

def LCS(X, Y):
    X, Y = " " + X, " " + Y 
    for i in range(1, len(X)-1):
        for j in range(1, len(Y)-1):
            if X[i] == Y[j]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j-1])

 

LCS 문자열을 찾는 방법 

별도의 테이블을 구성하여 dp가 어디서 왔는지 기록합니다. 

만약 왼쪽 대각선에서 왔다면 1, 위쪽에서 왔으면 2, 왼쪽에서 왔으면 3을 저장하여 1일 때만 문자를 추가합니다.

슈도코드는 다음과 같습니다.

def LCS(X, Y):
    X, Y = " " + X, " " + Y
    for i in range(1, len(X)-1):
        for j in range(1, len(Y)-1):
            if X[i] == Y[j]:
                dp[i][j] = dp[i-1][j-1] + 1
                backTrack[i][j] = 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j-1])
                backTrack[i][j] = 2 if dp[i - 1][j] > dp[i][j-1] else 3

 

 

백준 9251 LCS 

문제

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

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

 

첫번째 제출 코드 (파이썬)

import sys
input = sys.stdin.readline
s1 = " " + input().strip()
s2 = " " + input().strip()
n, m = len(s1)-1, len(s2)-1
dp = [[0]*(m+1) for _ in range(n+1)]
#왔던 길을 다시 돌아가 LCS의 문자들을 찾음
backTrack = [[0]*(m+1) for _ in range(n+1)]

for i in range(1, n+1):
    for j in range(1, m+1):
        if s1[i] == s2[j]:
            dp[i][j] = dp[i-1][j-1] + 1
            backTrack[i][j] = 1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])
print(dp[n][m])

 

백준 9252 LCS 2

문제

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

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를, 둘째 줄에 LCS를 출력한다.

LCS가 여러 가지인 경우에는 아무거나 출력하고, LCS의 길이가 0인 경우에는 둘째 줄을 출력하지 않는다.

예제 입력 

ACAYKP
CAPCAK

예제 출력 

4
ACAK

첫번째 제출 코드 (파이썬)

import sys
def getLCS(arr, n, m):
    i, j = n, m
    ans = ""
    while i > 0 and j > 0:
        if arr[i][j] == 1:
            ans += s1[i]
            i, j = i - 1, j - 1
        elif arr[i][j] == 2:
            i -= 1
        else:
            j -= 1
    return ans[::-1]

input = sys.stdin.readline
s1 = " " + input().strip()
s2 = " " + input().strip()
n, m = len(s1)-1, len(s2)-1
dp = [[0]*(m+1) for _ in range(n+1)]
#왔던 길을 다시 돌아가 LCS의 문자들을 찾음
backTrack = [[0]*(m+1) for _ in range(n+1)]

for i in range(1, n+1):
    for j in range(1, m+1):
        if s1[i] == s2[j]:
            dp[i][j] = dp[i-1][j-1] + 1
            backTrack[i][j] = 1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])
            backTrack[i][j] = 2 if dp[i-1][j] > dp[i][j-1] else 3
print(dp[n][m])
print(getLCS(backTrack, n, m))

 

결과 및 정리

LCS 문제를 풀다가 DP는 왜 대각선은 1을 더해주고 왼쪽과 위쪽은 큰 값을 넣어주는지 이해가 안되었는데 재귀를 통한 문제 풀이를 알고나니 그 원리가 바로 이해되었습니다.

오랜만에 길게 글을 써서 힘들었지만 그래도 LCS 만큼은 확실하게 집고 넘어 간거같아 만족합니다.