Vision Igniter: 9월 2017

언어가 뭐시 중헌디, 이겠지만 교육 / 강화학습 관련으로 간만에 Python으로 Dynamic Programming을 짜본 김에 오랜만에 Algorithm정리도 하며 기록을 남김.

* 강화학습(Reinforcement Learning)에서 MDP (Markov Decision Process)에서의 상태 천이는, 이전 State까지의 연산결과 값을 이용하기 때문에 Dynamic Programming Technique과 직접적으로 연관된다.

(벌써 10년도 더 전에 ㅠㅠ C로 복잡스럽게 짰던 기억이 아련히 스쳐간다.)

o 문제 정의

Input Text에서 Palindrome의 최대 길이 구하기. Longest Palindrome Substring, Search 등으로 보통 이야기 하는 문제.
Palindrome은 우리말로 '회문'이라 한다. "madam"처럼 앞으로 읽으나, 역순으로 읽으나 똑같은 단어/어절이 되는 문자열을 의미한다.

o Dynamic Programming
Dynamic Programming로 풀수 있는 문제는 두 가지 특성을 만족한다.

Optimal Substructure

Subproblem들의 솔루션을 조합하여 Global Optimum을 구할 수 있다.
즉 이전 단계(Subproblem 1)의 Best솔루션 + 현재 단계(Subproblem 2)의 Best Solution = 다음 단계의 Best 솔루션

Overlapping Subproblem

점화식을 가지는 Recursion 구조라 생각하면 쉽다. 대표적으로 피보나치 수열처럼 이전 단계의 Subproblem의 해를 다음 단계를 위해 재귀적으로 계속 재이용한다.

상기 이유로, DP를 짜기 위해서는 문제를 점화식 구조로 바꿀 수 있어야 한다. 그럼 Palindrome 문제를 점화식 문제로 정의해보자.

o Palindrome 문제의 점화식 (Recurrence Formula)

f(text) = ...

0, if n = 0

text 길이가 0이면 당연히 longest value = 0

1, if n = 1

text 길이가 1이면 당연히 longest value = 1

2 + f(text[2:n-1]), if n>1 and text[1] = text[n]

n이 1 이상이고 첫글자와 끝 글자가 같은경우 (예를 들어 "madam" 같은 경우)
일단 길이가 2 이상이니 2 + f(ada) 수행

max(f(text[1:n-1]), f(text[2:n]), if n>1 and text[1] != text[n]

첫글자와 끝 글자가 다른 경우, (예를 들어... "abededeaace" 와 같은 경우)
첫글자를 제외한 f(bededeaace), 끝 글자를 제외한 f(abededeaac) 중 큰 값을 취한다.

o 위 점화식을 그대로 Recursion Version으로 구현해보자.

def computeLongestPalindrome_recur(text):
    input_len = len(text)
    
    if input_len == 0: 
        return 0
    
    elif input_len == 1: 
        return 1
    
    elif (input_len > 1) and (text[0] == text[-1]): 
        return 2 + computeLongestPalindrome_recur(text[1:input_len-1])
    
    elif (input_len > 1) and (text[0] != text[-1]):
        return max(computeLongestPalindrome_recur(text[:input_len-1]), computeLongestPalindrome_recur(text[1:input_len]))
    
    return 0

이 짧은 몇줄로 구현되는건 신나지만 계산 복잡도가 높기 때문에, text가 조금만 길어져도 답을 구하는게 불가능할 정도로 계산시간이 엄청나게 증가한다.

o DP Version Code
Optimal Substructure, Overlapping Subproblem 특성을 이용하려면 이를 어딘가에 저장해두고 재이용하면서 점진적으로 다음 step을 계산해 나가야 한다.

C, C++에서는 전역적으로 이 Overlapping subprogram 결과물을 저장할 변수를 array로 미리 정의하여 잘 만들어두고 index로 access 해야 한다. 하지만 Python에서는 collection의 defaultdict를 쓰면 이 과정이 너무너무x100 간단하게 해결된다. (사랑해요 파이썬 -.-)

각 위의 각 step에서 계산 결과물을 저장할 공간을 두는 것 외에는 코드가 거의 똑같다.

from collections import defaultdict

memory = defaultdict(int)

def computeLongestPalindrome(text):
    if text in memory: 
        return memory[text]
    else:
        text_length = len(text)

        if text_length == 0:
            return 0

        elif text_length == 1:
            return 1

        else:
            if text[0] == text[-1]:
                memory[text] = 2 + computeLongestPalindrome(text[1:-1])
            else:
                memory[text] = max([
                    computeLongestPalindrome(text[:-1]), 
                    computeLongestPalindrome(text[1:])
                ])
            return memory[text]

약간만 긴 string으로 두 버전을 테스트해보면 어마어마한 속도차이를 체감할 수 있을 것이다.

Vision Igniter

2017년 9월 5일 화요일

Python Dynamic Programming (Longest Palindrome)

프로필