* 강화학습(Reinforcement Learning)에서 MDP (Markov Decision Process)에서의 상태 천이는, 이전 State까지의 연산결과 값을 이용하기 때문에 Dynamic Programming Technique과 직접적으로 연관된다.
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의 해를 다음 단계를 위해 재귀적으로 계속 재이용한다.
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으로 두 버전을 테스트해보면 어마어마한 속도차이를 체감할 수 있을 것이다.
