최장 공통 부분 서열 문제 (LCS)

두 문자열 X, Y가 주어졌을 때, X, Y에서 공통으로 나타나는 부분 문자열을 찾고자한다. 이때 부분 문자열중 길이가 최대인 부분서열을 찾는 방법은 뭐가 있을까?

 

문자서열 X, Y가 다음과 같이 있다고 하자.

 

X = A, B, C, B, D, A, B

Y = B, D, C, A, B, A

 

X, Y의 길이가 짧으니 눈대중으로도 최장 공통 부분 서열을 찾을 수 있을 것이다.

위 예시에서 최장 공통 부분 서열은, LCS(X, Y) = B, C, B, A 이다.

 

이 문제를 브루투 포스로 접근하면 X의 모든 부분서열 중에서 Y의 부분서열인 것들의 길이를 구한뒤 이 길이들 중에서 최대값을 찾으면 된다. 이때, X의 모든 부분 서열의 갯수는 2^n의 시간복잡도를 가지는데 절대 좋은 방법이 아닐것이다!

 

길이가 최대인 부분서열을 찾는문제, 즉 최적화 문제임을 알 수 있고 최적화 문제를 접했을 때는 DP를 사용해봄이 바람직하다. 실제로 LCS는 대표적인 DP(Dynamic Programming) 문제이다.

 

동적 계획법을 적용하기 전, 점화식을 찾기위해 공통 부분 서열을 찾는 방법을 재귀적인 관점에서 찾아보자.

 

길이가 m, n인 문자열 x, y가 있다고 하자. 공통 부분 서열을 찾을려면 두 가지 경우가 생기는데 아래와 같다.

 

1) xm과 yn이 같을 때

공통 부분 서열인 z가 다음과 같이 있을 때, 만약 xm과 yn이 같다면 공통인 부분을 찾은것이므로 z에 붙혀주면된다. 그리고 문자서열 x, y 에서 한 칸 줄인 부분부터 다시 공통 부분 수열을 찾으면 된다. 이 때 공통부분서열의 길이는 1증가한다.

 

두 문자서열의 마지막 글자가 같을 경우

2) xm과 yn이 같지 않을 때, 2가지 경우의 수가 있다.

        2 - 1 문자 서열 x를 한칸 줄이고 다시 공통 서열을 찾는 경우

 

z = LCS(xm-1, yn)

 

        2 - 2 문자 서열 y를 한칸 줄이고 다시 공통 서열을 찾는 경우이다.

 

z = LCS(xm, yn-1)

 

두 문자서열의 끝 자리가 다를경우

 

이제 재귀적으로 정의해보도록 하자.

 

c(i, j)를 문자서열 xi와 yj의 최장 공통부분서열의 길이라고 하자. 그리고 재귀식이 종료되는 조건은 두 서열중 하나라도 길이가 0이 된다면 공통서열의 길이는 0이 됨으로, i = 0 또는 j = 0이되면 c(i, j)는 0이 된다.

 

재귀식은 다음과 같다.

1. xi = yj 일때, c(i, j) = c(i - 1, j - 1) + 1

 

2. xi ≠ yj 일때, c(i, j) = max(c(i - 1, j), c(i, j - 1))

 

코드로 나타내면 다음과 같다.

def lcs(x,y):
    m, n = len(x), len(y)
    if m == 0 or n == 0:
        return 0
    else:
        if x[-1] == y[-1]:
            return lcs(x[:x-1], y[:y-1]) + 1
        else:
            return max(lcs(x, y[:y-1]), lcs(x[:x-1], y))

 

하지만 재귀를 사용하면, 특정 부분 서열을 중복해서 만들게 된다. 이때 중복을 피하기위해 이미 만들어둔 값이라면 배열에 저장해뒀다가 계산없이 바로 쓸 수 있도록 메모이제이션을 적용해보자.

 

def lcs(x,y):
    # 인덱스 1부터 접근하기위해
    x, y = [' '] + x, [' '] + y
    m, n = len(x), len(y)
    dp = [[0 for _ in range(n)] for_ in range(m)]
    
    for i in range(1, m):
        for j in range(1, n):
            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])
    return dp

 

---

이제는 각 케이스에서 세 경우의 수를 고려하며 dp 테이블에 값을 채워넣어가 보자.

 

dp[i-1][j-1] + 1 에서 값을 가져오거나, dp[i-1][j], dp[i][j-1] 중 큰 값을 가져오면 된다.

 

이렇게 값을 구하고 테이블에 넣으면 다음과 같다. 그리고 우리가 찾을 가장 긴 수열은 dp[7][6]에 있는 값이다. 즉, 4인것을 알 수 있다.

	0	B	D	C	A	B	A
0	0	0	0	0	0	0	0
A	0	0	0	0	1	1	1
B	0	1	1	1	1	2	2
C	0	1	1	2	2	2	2
B	0	1	1	2	2	3	3
D	0	1	2	2	2	3	3
A	0	1	2	2	3	3	4
B	0	1	2	2	3	4	4

 

---

이제 해당 문제를 풀어보자!! 문제 제목부터 LCS이다 ㅎㅎ

 

9251번: LCS

9251번: LCS

 

완성된 코드는 다음과 같다. 위 설명과 동일하게 각 칸에서 세가지 경우의 수를 고려해서 최장 길이를 찾아내면 된다.

 

# LCS
import sys

a = list(sys.stdin.readline().rstrip())
b = list(sys.stdin.readline().rstrip())

x = [' '] + a
y = [' '] + b

m, n = len(x), len(y)
c = [[0 for _ in range(n)] for _ in range(m)]

for i in range(1, m):
    for j in range(1, n):
        if x[i] == y[j]:
            c[i][j] = c[i-1][j-1] + 1
        else:
            c[i][j] = max(c[i-1][j], c[i][j-1])

print(c[m-1][n-1])