알고리즘 - 최장 공통 부분 순서

최장 공통 부분 순서(LCS: Longest Common Subsequence)

• 부분 순서: 어떤 시퀀스의 일부분으로 상대적인 순서를 유지하는 것
• LCS 문제는 두 데이터에 공통으로 들어 있는 부분 순서 중에서 가장 긴 것을 찾는 문제

LCS 길이의 순환 관계식

• 길이가 각각 m과 n인 두 문자열 X, Y이 주어졌을 때 LCS 길이를 구하려고 함

기반 상황

• n이나 m이 0이라면 두 문자열 중 하나의 길이가 0이고, 공통 문자가 없으므로 LCS의 길이는 0

일반 상황

• 핵심 아이디어는 X와 Y의 맨 뒤의 문자부터 처리하는데, 그 문자들이 같은 경우와 다른 경우로 분리하여 처리하는 것

• Case 1. X와 Y의 마지막 문자가 같은 경우 이 문자를 X와 Y에서 모두 빼고 LCS 길이를 구한 다음 1을 더하면 된다

• Case 2. X와 Y의 마지막 문자가 다른 경우 X에서 마지막 문자를 빼고 Y와 비교하는 것과 반대로 Y에서 하나를 빼고 X와의 LCS를 구하는 것

• 따라서 순환 관계로 나타낼 수 있다

순환구조의 알고리즘

LCS의 길이(분할 정복)

def lcs_recur(X, Y, m, n): 
    if m == 0 or n == 0: 			# base case 
        return 0 
    elif X[m-1] == Y[n-1]: 		# case 1: x_m == y_n
        return 1 + lcs_recur(X, Y, m-1, n-1) 
    else: 						# case 2
        return max(lcs_recur(X, Y, m, n-1), lcs_recur(X, Y, m-1, n)) 

동적 계획법(테이블화)에 의한 LCS 길이

• 테이블 준비: 부분 해 저장할 테이블 이름: L, L의 크기는 (m+1) x (n+1)이다.

LCS 길이 알고리즘

def lcs_dp(X , Y): 
    m = len(X) 
    n = len(Y) 
    L = [[None]*(n+1) for _ in range(m+1)] 	# 테이블 생성
  
    for i in range(m+1): 
        for j in range(n+1): 
            if i == 0 or j == 0 :		# base case: 하나의 길이라도 0이면
                L[i][j] = 0			# LCS --> 0
            elif X[i-1] == Y[j-1]:	# 마지막 글자가 같으면
                L[i][j] = L[i-1][j-1]+1
            else:					# 마지막 글자가 다르면
                L[i][j] = max(L[i-1][j], L[i][j-1])

    for i in range(m+1):
        print(L[i])
    # L[m][n] contains the length of LCS of X[0..n-1] & Y[0..m-1] 
    print("LCS = ", lcs_dp_traceback(X, Y, L))

    return L[m][n] 

• 시간 복잡도는 $O(mn)$ 이고 lcs_recur()에 비해 엄청난 개선

LCS 추적 알고리즘

LCS 테이블에서 LCS를 추적하는 알고리즘

def lcs_dp_traceback(X, Y, L):
    lcs = ""													# ①
    i = len(X)													# ②
    j = len(Y)													# ② 
    while i > 0 and j > 0:
        v = L[i][j] 
        if v > L[i][j-1] and v > L[i-1][j]  and v > L[i-1][j-1]:# ③
            i -= 1
            j -= 1
            lcs = X[i] + lcs

        elif v == L[i][j-1] and v > L[i-1][j]: j -= 1			# ④
        else : i -= 1											# ⑤

    return lcs

LCS 테스트 프로그램

X = "GAME OVER"
Y = "HELLO WORLD"
print("X = ", X)
print("Y = ", Y)
print("LCS(분할 정복)", lcs_recur(X , Y, len(X), len(Y)))
print("LCS(동적 계획)", lcs_dp(X , Y) )

테스트 결과

X =  GAME OVER
Y =  HELLO WORLD
LCS(분할 정복) 4
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2]
[0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3]
[0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3]
[0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3]
[0, 0, 1, 1, 1, 2, 2, 2, 3, 4, 4, 4]
LCS =  E OR
LCS(동적 계획) 4