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

동적 계획법이란 복잡한 문제를 재귀를 통해 간단한 하위 문제로 단순화하여 해결하는 방법이다. 문제가 최적 부분 구조와 중복되는 부분 문제를 갖고 있다면 동적 계획법으로 해겨랄 수 있다.

1. 메모이제이션

동일한 계산을 반복할 때 이전에 계산한 값을 메모리에 저장하여 중복 계산을 제거하여 실행 속도를 빠르게 하는 기법이다.

1.1 피보나치 수열

# 데코레이터를 이용한 방법
from functools import wraps

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

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

14930352

# 리스트를 이용한 방법


def fib3(memo, n):
    if memo[n] == 0:
        memo[n] = fib3(memo, n-2) + fib3(memo, n-1)
    return memo[n]


n = 35

memo = [0] * (n+1)
memo[0], memo[1] = 1, 1
fib3(memo, n)

14930352

2. 연습문제

2.1 최장 증가 부분열

오름차순으로 숫자를 고른 부분열의 길이가 최대가 되는 경우를 구하라.

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


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)

    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 wrapper(*args):
        if args not in cache:
            cache[args] = func(*args)
        return cache[args]
    return wrapper


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
    print(end)
    return len(end)


s1 = [94, 8, 78, 22, 38, 79, 93, 8, 84, 39]
print(naive_longest_inc_subseq(s1))
print(memoized_longest_inc_subseq(s1))
print(dp_longest_inc_subseq(s1))
print(longest_inc_bisec(s1))

5
5
5
[8, 8, 38, 39, 84]
5