35. 동적 계획법 - 가장 긴 공통 문자열 찾기 - 파이썬

동적 프로그래밍((dynamic programming)을 적용하기 쉬운(?) 예제로 가장 긴 공통 문자열 찾기(LCS, Longest Common Substring)가 있습니다. 

 

두 개의 문자열 'abcde'와 'cdefg'에서 가장 긴 공통 문자열은 'cde'입니다. 

 

먼저 전수조사(brute force)로 답을 찾아보고 문제점을 알아봅니다. 

def make_set(s):
    result = set()
    for i in range(len(s)):
        for j in range(i + 1, len(s) + 1):
            result.add(s[i:j])
    return result


def lcs(s1, s2):
    max_len = 0
    max_str = ''
    for each in make_set(s1) & make_set(s2):
        if len(each) > max_len:
            max_len = len(each)
            max_str = each
    print(max_len, max_str)
    # return max_len, max_str


lcs('abcde', 'cdeab')

파이썬의 집합 자료형을 이용하는 방법입니다.
집합 자료형은 원소의 중복을 막아줍니다. 
그리고 교집합을 이용하면 이 문제를 간단히 풀 수 있습니다. 

 

흔히 말하는 노가다 전수조사형 풀이법입니다.
가능한 문자열을 모두 뽑아서 비교합니다.

 

하지만 조금만 단어가 길어져도
시간이 너무 오래 걸립니다. 

 

(최대 공통 문자열의 길이만) 재귀적으로 풀어봅니다. 

# Longest Common Substring / recursive


def lcs(i, j):
    if i == word1_length or j == word2_length:
        return 0
    if word1[i] == word2[j]:
        return 1 + lcs(i + 1, j + 1)
    else:
        return max(lcs(i + 1, j), lcs(i, j + 1))


word1 = 'abcde'
word2 = 'cdefab'
word1_length = len(word1)
word2_length = len(word2)
print(lcs(0, 0))  # 3

 

(최대 공통 문자열의 길이만) 리스트(배열)를 이용해 풀어봅니다. 

공통 문자열의 길이를 저장할 2차원 리스트가 핵심입니다. 
공통 문자열이 길어질수록 저장되는 숫자도 1씩 커집니다. 

이 2가지만 이해하면 코딩은 어렵지 않습니다. 

def show(array):
    for i in array:
        print(i)


def lcs_dp():
    array = [[0 for _ in range(len(word2)+1)] for _ in range(len(word1)+1)]
    for i in range(len(word1)):
        for j in range(len(word2)):
            if word1[i] == word2[j]:
                array[i+1][j+1] = array[i][j] + 1
    show(array)


word1 = 'abcde'
word2 = 'cdefab'

lcs_dp()

[0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 1, 0]
[0, 0, 0, 0, 0, 0, 2]
[0, 1, 0, 0, 0, 0, 0]
[0, 0, 2, 0, 0, 0, 0]
[0, 0, 0, 3, 0, 0, 0]

위 배열을 보면 공통 문자열이 길어질수록 사선 방향(↘)으로 숫자가 커집니다.

3이 가장 큰 숫자군요. 이 숫자가 가장 긴 문자열의 길이가 됩니다. 

그리고 3의 배열 내에서의 위치(정확하게 말하면 1을 빼야 함)가 문자열의 마지막 글자의 위치가 됩니다. 

 

문자열까지 찾을 수 있도록 코드를 추가합니다. 

# Longest Common Substring / dynamic programming


def lcs(word1, word2):
    max = 0
    index = 0
    letters = [[0 for _ in range(len(word2) + 1)] for _ in range(len(word1) + 1)]
    for i in range(len(word1)):
        for j in range(len(word2)):
            if word1[i] == word2[j]:
                letters[i+1][j+1] = letters[i][j] + 1
            if max < letters[i+1][j+1]:
                max = letters[i+1][j+1]
                index = i + 1
    return word1[index-max:index]


print(lcs('aabcc', 'babcd'))

abc

아까 말씀드렸던 가장 큰 숫자 3을 별도의 반복 없이 기존 for문 내에서 찾을 수 있도록 코딩합니다. 

가장 큰 숫자를 찾으면 그때의 인덱스도 같이 저장합니다.