동적 계획법

- 다이나믹 프로그래밍 참고: 동적 계획법

- 다이나믹 프로그래밍((Dynamic Programming)으로도 불림

- 큰 문제를 작은 문제로 나눠서 푸는 방법

- 분할 정복과 유사하지만...

동적 계획법 분할 정복
공통점 큰 문제를 작은 문제로 나눠서 해결 큰 문제를 작은 문제로 나눠서 해결
차이점 작은 문제가 반복됨 작은 문제가 반복되지 않음

- 나중에 분할 정복에 대해서도 다뤄보자

다이나믹 프로그래밍 조건

1. 작은 문제들의 반복

2. 같은 문제는 구할 때마다 정답이 같음

다이나믹 프로그래밍 구현

- 모든 작은 문제는 단 한번만 풀어야 함

- 정답을 구한 작은 문제는 어딘가에 저장

- 큰 문제를 해결할 때 미리 구한 작은 문제의 정답을 사용

  • 피보나치 수열을 다이나믹 프로그래밍으로 구현해보자

Top-down

- 큰 문제를 해결할 때 작은 문제가 해결되지 않았으면 작은 문제를 해결하여 큰 문제를 해결

- 재귀 함수로 구현하는 경우가 Top-down 방법

- 메모이제이션 기법 사용 ---> 미리 구한 작은 문제의 정답을 어딘가에 저장

- 단순 재귀 함수로 구현한 피보나치 함수의 시간 복잡도는 $T(n) = T(n-1) + T(n-2) + C$이다

- 하지만 Top-down 방법을 사용한 피보나치 함수의 시간 복잡도는 $T(n) = T(n-1) + C$이다

- 왜냐하면 메모이제이션을 통해 피보나치 함수값을 $T(n-1)$을 재귀호출 하면서 미리 구해놨기 때문에

- $T(n-2)$에서는 재귀호출이 일어나지 않아 상수시간만 소요된다

fibonacci = {0: 0, 1: 1}  # 메모이제이션을 위한 딕셔러니 선언


def fibo_top_down(n):
    if n in fibonacci:
        return fibonacci[n]
    fibonacci[n] = fibo_top_down(n - 1) + fibo_top_down(n - 2)
    return fibonacci[n]
fibo_top_down(10)
55

Bottom-up

- 작은 문제부터 차근차근 해결하여 큰 문제를 해결

- 반복문 사용

def fibo_bottom_up1(n):
    if n <= 1:
        return n
    fir_fibo = 0
    sec_fibo = 1
    for _ in range(n - 1):
        next_fibo = fir_fibo + sec_fibo  # 2번째 피보나치 값 = 0번째 피보나치 값 + 1번째 피보나치 값 (n번째 피보나치 값 = n-2번째 피보나치 값 + n-1번째 피보나치 값)
        fir_fibo = sec_fibo  # 0번째 피보나치 값을 1번째 피보나치 값으로 업데이트
        sec_fibo = next_fibo  # 1번째 피보나치 값을 2번째 피보나치 값으로 업데이트 
        # 다시 for문 시작으로 돌아가서 1번째 피보나치 값과 2번째 피보나치 값을 통해 3번째 피보나치 값을 구함 (이를 n-1번 반복)
        # for 문의 역할은 점화식을 통해 0번째와 1번째의 피보나치 값을 가지고 n번째의 피보나치 값을 구한다
    return next_fibo
fibo_bottom_up1(10)
55

- 또 다른 방법

- 미리 dp라는 list를 생성

x = 100  # 문제 조건에 맞춰서
dp = [-1] * x  # 리스트 초기화


def fibo_bottom_up2(n):
    dp[0] = 0
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]
fibo_bottom_up2(10)
55

- bottom-up 방식으로 구현한 위의 두개 코드의 차이점은?

- fibo(9)fibo(10)을 구할 때 처음 코드는 fibo_bottom_up1(9)fibo_bottom_up1(10) 총 함수를 2번 사용

- 사실 fibo_bottom_up1(10)을 계산했다면 fibo_bottom_up1(9)도 당연히 알지만 각각을 따로 두 번 구했다

- 첫 번째 코드의 경우 다이나믹 프로그래밍은 이미 구한 작은 문제 정답은 또 구하지 않기로 했지만 그렇지 않은 모습

- 하지만 두 번째 코드는 fibo_bottom_up2(10)을 계산했다면 $\operatorname{dp}[0]$ ~ $\operatorname{dp}[10]$까지 값이 채워져 있기에 fibo_bottom_up2(9)를 계산하지 않고 $\operatorname{dp}[9]$를 통해 fibo(9)를 계산할 수 있음

- 하지만 공간복잡도(메모리 사용) 측면으로 보면 첫 번째 코드가 두 번째 코드보다 메모리를 덜 잡아먹는다 (두 번째 코드는 충분히 큰 배열이 필요함)

- 결론: 상황에 맞게 사용하자