Dynamic programming - 동적 프로그래밍

효율적으로 문제를 해결하기 위한 기술로 문제를 작게 쪼깨어 해결한다.

• 일반적으로 재귀적인 방법을 사용하여 복잡한 문제를 간단하게 만든다.
• 동적 프로그래밍을 적용하여 해결할 수 있는 문제는 반드시 하위 문제로 쪼갤 수 있다.
  • 최적의 하위구조(optimal substructure)를 가지고 있다고 표현함
• 캐싱과 같은 방식을 사용하는 Memoization 기법을 사용할 수 있음
• Divide&Concuer과 유사하지만 동적 프로그래밍은 작은 문제가 중복되지 않는다.

VS Greedy

• 그리디 알고리즘은 지역적 최적의 해를 찾는다는 점에서 차이가 있다.

Example Code(Fibonacchi)

import sys
import time
from typing import Callable

input = sys.stdin.readline


def fibo(n: int) -> int:
    if n == 1 or n == 0:
        return 1
    return fibo(n - 1) + fibo(n - 2)


def fibo_memoization(n: int) -> int:
    global fibo_cache

    if fibo_cache[n] == 0:
        fibo_cache[n] = fibo_memoization(n - 1) + fibo_memoization(n - 2)

    return fibo_cache[n]


def check_time(func: Callable[[int], int], n: int):
    start_time = time.time()
    for i in range(n):
        func(i)
    print("execution time : {}".format(time.time() - start_time))


N = int(input())

fibo_cache = [0] * (N + 1)
fibo_cache[0] = 1
fibo_cache[1] = 1

check_time(fibo, 30)  # recommend not to try
check_time(fibo_memoization, N)

참고

https://en.wikipedia.org/wiki/Dynamic_programming
https://www.programiz.com/dsa/dynamic-programming