동적 계획법 예제2: Longest Common Subsequence 문제

먼저 문자열의 sub sequence는 문자열에 속한 각 문자의 순서를 유지한 채 만들 수 있는 부분집합입니다. 예를 들어 'AB'라는 문자열이 있는 경우 빈 문자열 ''와 'A', 'B', 'AB'가 모두 seb sequence가 됩니다. 'BA'는 순서가 바뀌었으므로 sub sequence가 되지 않습니다.

 

두 문자열 X, Y가 있을 때 문자열 간에 공통된 sub sequence 중 가장 긴 sequence의 길이를 구해보도록 합시다.

X, Y의 길이가 길어짐에 따라 X의 sub sequence를 뽑아내서 다시 Y의 sub sequence들과 비교하도록 하는 brute force 방식으로 접근하기에는 연산량이 너무나 많아집니다. 이런 경우 보통 동적 계획법을 통해 해결 가능한 문제가 아닌지 의심해야 합니다.

 

동적 계획법 문제를 해결하기 위해서는 현재 문제를 보다 작은 문제로 나눌 수 있어야 합니다. 이를 위해 문자열 X, Y는 각각 다음과 같다고 가정해봅니다.

• X = 'ABCD'
• Y = 'ABED'

다음 순서에 따라 문제를 해결해 갑니다.

1. 우선 문자열 X와 Y의 가장 마지막 인덱스에 해당하는 원소부터 훑어갑니다. X[3]과 Y[3]은 'D'로 같습니다. LCS의 길이는 1이 됩니다.
   • get_lcs_len('ABCD', 'ABED') = get_lcs_len('ABC', 'ABE') + 1
2. X[2] = 'C', Y[2] = 'E'로 동일하지 않습니다. 이런 경우 X[0] ~ X[1]과 Y의 LCS와 X와 Y[0]~Y[1]의 LCS  길이 중 더 큰 값을 index 0 ~ 2 사이의 LCS라고 봅니다.
   • get_lcs_len('ABC', 'ABE') = max(get_lcs_len('AB', 'ABE'), get_lcs_len('ABC', 'AB'))
3. 1, 2의 과정을 반복해가면 X 또는 Y의 문자열을 모두 확인한 시점에 ( == 비교할 문자열의 길이가 0이 되는 경우) 반복을 종료합니다. (재귀호출로 구현할 경우 0을 반환하여 종료합니다.)
4. 마지막의 LCS 길이가 얻고자 하는 해가 됩니다.

이를 python 코드로 옮겨 봅시다.

def get_lcs_len(X, Y):
    length_of_X = len(X)
    length_of_Y = len(Y)
    if length_of_X == 0 or length_of_Y == 0:
        return 0
    if X[length_of_X - 1] == Y[length_of_Y - 1]:
        return 1 + get_lcs_len(X[:length_of_X - 1], Y[:length_of_Y - 1])
    else:
        return max(get_lcs_len(X[:length_of_X - 1], Y), get_lcs_len(X, Y[:length_of_Y - 1]))
    
X= 'ACB'
Y= 'ABC'
print(get_lcs_len(X, Y))

가장 끝 요소가 동일할 때는 큰 문제가 되지 않지만 다를 경우 두 번의 재귀 호출을 진행해야만 결과를 얻을 수 있습니다. O(2^n)의 시간 복잡도가 되어버립니다. 매우 비효율적이라 할 수 있습니다.

 

topdown 방식의 동적 계획법을 사용하여 시간 복잡도를 개선해보도록 합니다.

재귀 호출 결과를 2차원 리스트에 저장해 놓고 반복되는 동일 연산을 피하는 방법입니다. 빈 문자열끼리의 LCS 길이도 확인해야 하기 때문에 2차원 리스트의 x, y 축은 각각 문자열 X, Y의 길이에 + 1 한 만큼의 크기로 작성합니다. 0번 인덱스가 빈 문자열이 됩니다. 2차원 리스트는 모두 0으로 초기화해줍니다.

memoization_table = [[0] * (len(Y) + 1) for _ in range(len(X) + 1)]


def get_lcs_len_memoization(X, Y):
    len_of_X = len(X)
    len_of_Y = len(Y)
    if (len_of_X == 0) or (len_of_Y == 0):
        return 0
    if memoization_table[len_of_X][len_of_Y] != 0:
        return memoization_table[len_of_X][len_of_Y]

    # 문자열의 마지막 글자를 비교해 조건에 따라 재귀 호출합니다.
    if X[len_of_X - 1] == Y[len_of_Y - 1]:
        memoization_table[len_of_X][len_of_Y] = get_lcs_len_memoization(X[:len_of_X - 1], Y[:len_of_Y - 1]) + 1
    else:
        memoization_table[len_of_X][len_of_Y] = max(get_lcs_len_memoization(X, Y[:len_of_Y - 1]),
                                                   get_lcs_len_memoization(X[:len_of_X - 1], Y))
    return memoization_table[len_of_X][len_of_Y]


X = 'ACB'
Y = 'ABC'
print(get_lcs_len_memoization(X, Y))
for e in memoization_table:
    print(e)

결과 출력 후 memoization을 위한 테이블의 데이터가 어떻게 변경되었는지 그 내용을 출력해 보면 다음과 같은 규칙을 찾아볼 수 있습니다.

• X[i - 1] == Y[j - 1] 인 경우 memoization_table[i][j] = memoization_table[i - 1][j - 1] + 1 이 됩니다.
• X[i - 1] != Y[j - 1] 인 경우 memoization_table[i][j] = max(memoization_table[i][j - 1], memmoization_table[i - 1][j]) 가 됩니다.

이를 바탕을 위의 코드를 bottomup 방식의 동적계획법 코드로 변경하면 다음과 같습니다.

def get_lcs_len_dp(X, Y):
    dp_table = [[0] * (len(Y) + 1) for _ in range(len(X) + 1)]
    for i in range(1, len(X) + 1):
        for j in range(1, len(Y) + 1):
            if X[i - 1] == Y[j - 1]:
                dp_table[i][j] = dp_table[i - 1][j - 1] + 1
            else:
                dp_table[i][j] = max(dp_table[i - 1][j], dp_table[i][j - 1])
    for e in dp_table:
        print(e)
    return dp_table[len(X)][len(Y)]


X = 'ACB'
Y = 'ABC'
print(get_lcs_len_dp(X, Y))