11. 동적 계획법 (Dynamic Programming): 파이썬 자료구조와 알고리즘

동적 계획법 (dynamic programming) 은 복잡하 문제를 재귀를 통해 간단한 하위 문제로 분류하여 단순화하여 해결하는 방법이다. 어떤 문제가 최적 부분 구조 (optimal substructure) 와 중복되는 부분 문제 (overlapping subproblem) 를 갖고 있다면 동적 계획법으로 해결할 수 있다.

 

최적 부분 구조는 답을 구하기 위해서 했던 계산을 반복해야 하는 문제의 구조를 말한다. 동적 계획법을 사용하려면 먼저 최적 부분 구조가 있는지 확인해야 한다. 동적 계획법은 부분 문제를 풀고 결과를 저장한 후 다음 부분 문제를 푸는 과정에서 저장된 결과를 사용한다.

 

메모이제이션

메모이제이션 (memoization) 은 프로그램이 동일한 계산을 반복할 때 이전에 계산한 값을 메모리에 저장하여 동일한 계산의 반복 수행을 제거하여 프로그램의 실행 속도를 빠르게 하는 기법이다. 동적 계획법의 핵심이라고 할 수도 있다.

 

피보나치 수열

파이썬과 같은 고급 언어는 반환 값을 캐싱하여 재귀식을 직접 구현할 수 있다. 같은 인수가 두 번 이상 호출되고 그 결과가 캐시에서 직접 반환되는 메모이제이션 메서드를 구현해보자.

 

이전에 피보나치 수열을 재귀 함수로 구현했었을 때 재귀적으로 함수를 호출했을 때 이전에 이미 처리했던 함수를 계속 다시 하는 문제가 있었다. 아래와 같이 중첩 함수를 사용하여 피보나치 수열 문제를 동적 계획법으로 해결할 수 있다.

 

아래 코드를 확인해보자. benchmark 함수는 함수의 시작과 끝 사이의 시간 (함수 실행 시간) 을 같이 출력한다.

 

from functools import wraps
import time

def memo(func):
    cache = {}

    @wraps(func)
    def wrap(*args):
        if args not in cache:
            cache[args] = func(*args)
        return cache[args]
    return wrap

def benchmark(method):
    @wraps(method)
    def timed(*args, **kw):
        ts = time.time()
        result = method(*args, **kw)
        te = time.time()
        print('{0} s'.format(te-ts))
        return result
    return timed

@memo
def fib_memo(n):
    if n < 2:
        return 1
    else:
        return fib_memo(n-1) + fib_memo(n-2)

def fib_without_memo(n):
    if n < 2:
        return 1
    else:
        return fib_without_memo(n-1) + fib_without_memo(n-2)

@benchmark
def test_memo(n):
    print(fib_memo(n))

@benchmark
def test_without_memo(n):
    print(fib_without_memo(n))

test_memo(35)
test_without_memo(35)

 

결과

 

PS C:\Users\bumsu\Desktop\Python\DSA> & C:/Python38/python3.exe "c:/Users/bumsu/Desktop/Python/DSA/Algorithm/11. 동적 계획법/memoized_fib.py"
14930352
0.0009970664978027344 s
14930352
3.1337695121765137 s

 

메모이제이션을 사용한 경우와 사용하지 않은 경우가 꽤나 극단적으로 차이가 난다. 이처럼 동적 계획법은 반복을 줄여주기 때문에 실행 시간을 비약적으로 줄일 수도 있다.

 

연습문제

최장 증가 부분열

메모이제이션의 또 다른 재미있는 예제는 주어진 리스트에서 최장 증가 부분열 (longest increasing subsequence) 을 찾는 문제다. 증가하는 순서대로 (오름차순으로) 숫자를 고른 부분열의 길이가 최대가 되게 하면 된다. 예를 들어 리스트 [94, 8, 78, 22, 38, 79, 93, 8, 84, 39] 가 있다고 하면, 가장 길게 증가하는 부분 리스트는 [8, 22, 38, 79, 93] 또는 [8, 22, 38, 79, 84] 가 된다. 잘 이해가 안된다면 아래 더보기를 눌러보자.

 

[94, 8, 78, 22, 38, 79, 93, 8, 84, 39] 를 보면, 증가하는 순서대로만 부분 리스트를 구해야한다. 먼저 [94] 가 있다. 그 다음 8을 시작으로 하는 부분 리스트는 [8, 78, 79, 84], [8, 78, 79, 93], [8, 22, 79, 84], 등등 이 있다.

 

책의 정답

 

from bisect import bisect
from itertools import combinations
from functools import wraps
from benchmark import benchmark

def naive_longest_inc_subseq(seq):
    for length in range(len(seq), 0, -1):
        for sub in combinations(seq, length):
            if list(sub) == sorted(sub):
                return len(sub)

def dp_longest_inc_subseq(seq):
    L = [1] * len(seq)
    res = []
    for cur, val in enumerate(seq):
        for pre in range(cur):
            if seq[pre] <= val:
                L[cur] = max(L[cur], 1 + L[pre])
    return max(L)

def memo(func):
    cache = {}
    @wraps(func)
    def wrap(*args):
        if args not in cache:
            cache[args] = func(*args)
        return cache[args]
    return wrap

def memoized_longest_inc_subseq(seq):
    @memo
    def L(cur):
        res = 1
        for pre in range(cur):
            if seq[pre] <= seq[cur]:
                res = max(res, 1 + L(pre))
        return res
    return max(L(i) for i in range(len(seq)))

def longest_inc_bisec(seq):
    end = []
    for val in seq:
        idx = bisect(end, val)
        if idx == len(end):
            end.append(val)
        else:
            end[idx] = val
    return len(end)

 

위에서부터 각 함수의 동작 방식을 분석해보자.

 

첫 번째 함수는 단순한 방법으로 이를 구현한다. 먼저 주어진 시퀀스의 길이를 줄여가면서 탐색을 하는데, combinations 함수는 itertools 모듈의 함수로써 해당 시퀀스에서 가능한 조합 (부분 시퀀스) 들을 구해준다. 그 후, 해당 부분 시퀀스를 정렬한 것과 정렬하지 않은 것이 같다면, 그 뜻은 최창 증가 부분열을 찾았다는 뜻이된다. 또한 for 반복문이 시퀀스의 길이부터 시작하는 이유는 해당 길이에서 증가 부분열을 찾을 수 없다면 다음 길이 (1 짧은 길이) 에서 증가 부분열을 찾는 작업을 반복해야 최장 증가 부분열을 찾을 수 있을 것이기 때문이다. itertools 의 combinations (와 permutations) 에 관한 내용은 아래 블로그 글을 참고하도록 하자.

 

https://itholic.github.io/python-combination-permutation/

[python] itertools를 이용해 순열과 조합 구하기

 

두 번째 함수는 동적 계획법으로 이를 구현하고, 세 번째 함수는 메모이제이션으로 이를 구현한다. 이 실행 과정은 다음 그림과 같다.

 

pre가 cur보다 작은 경우 (cur보다 작은 항목이 오름차순 항목의 후보가 될 수 있다), L[pre]를 1 증가시켜 L[cur]과 비교하여 큰 값을 다시 L[cur]에 저장한다 (cur에서 pre의 항목을 비교 진행하는 과정에서 cur 기준으로 pre 항목들이 오름차순으로 증가하는지 계산한다). pre가 cur보다 큰 경우 L[cur] 값을 유지하며, 최종 결과는 [1,1,2,2,3,4,5,2,5,4] (초록색) 이며, 최댓값은 5이다.

 

출처

파이썬 자료구조와 알고리즘 - 한빛미디어, 미아 스타인