다이나믹 프로그래밍 (Dynamic Programming, 동적 계획법)

DP란 '하나의 문제는 단 한 번만 풀도록 하는 알고리즘'

다이나믹 프로그래밍은 메모리 공간을 약간 더 사용해서 연산 속도를 비약적으로 증가시키는 방법
이미 진행이 되었던 연산이 반복되는 결점을 보안하기 위해 고안함.
=> 여러개의 소문제로 분할하여 각 소문제의 해결안을 바탕으로 주어진 문제를 해결, 이때 각 소문제는 다시 여러개의 소문제로 분할 가능

다음 2가지 조건을 만족할 때 사용 가능

• 큰 문제를 작은 문제로 나눌 수 있다.
• 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다

위 조건을 만족하는 대표적인 문제가 피보나치 수열
(피보나치 수열은 특정한 숫자를 구하기 위해 그 앞에 있는 숫자와 두 칸 앞에 있는 숫자의 합)
피보나치 수열의 점화식 : D[i] = D[i-1] + D[i-2]

<재귀함수를 이용한 피보나치 수열 구현>

import time

d = [0] * 50

def fibo(x):
    if x == 1 or x == 2:
        return 1
    if d[x] != 0:
        return d[x]
    d[x] = fibo(x-1) + fibo(x-2)
    return d[x]

for num in range(5, 40, 10):
    start = time.time()
    res = fibo(num)
    print(res, '-> 러닝타임:', round(time.time() - start, 2), '초')

<반복문을 이용한 피보나치 수열 구현>

d = [0] * 100

d[1] = 1 # 첫 번째 항
d[2] = 1 # 두 번째 항
N = 99   # 피보나치 수열의 99번째 숫자는?

for i in range(3, N+1):
    d[i] = d[i-1] + d[i-2]

print(d[N])

동적 계획법

1. Memoization (Top-Down, 하향식)

하향식(Top-Down) 경우 하위 문제에 대하여 정답을 계산했는지 확인해가며 문제를 자연스럽게 풀어가는 방법
< 동일 계산 반복시 >
이전 계산값을 메모리에 저장하여 (메모리 공간을 약간 더 사용) (캐싱이라고도 함)

def fibonacci_memoi(num):
    global memo
    if num >= 2 and len(memo) <= num:
        memo.append(fibonacci_memoi(num-1) + fibonacci_memoi(num-2))
    return memo[num]
memo = [0, 1]

2. Tabulation (Bottom-up, 상향식)

최초 값부터 차례대로 계산해 나가는 방식

def fibonacci_dp(num):
    f = [0, 1]
    for i in range(2, num+1):
        f.append(f[i-1] + f[i-2])
    return f