📌다이나믹 프로그래밍란?

다이나믹 프로그래밍은 문제를 해결할 때 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다.
그리고 하나의 문제는 단 한 번만 풀도록 하는 문제 해결 방법이다.

📌다이나믹 프로그래밍 사용의 조건

dp를 사용할 때는 밑의 3개 조건이 맞아야 한다.

1. problem이 sub-problem으로 쪼개질 때.
2. sub-problem으로 problem을 구할 수 있을 때.
3. sub-problem이 겹칠 때.(값을 보관해서 중복을 없앤다.)

📌다이나믹 프로그래밍 접근 방법

1. 재귀
2. 보관(memoization)
3. 바텀-업(bottom-up), 탑-다운(top-down)

📌다이나믹 프로그래밍 사용 예시

✨대표적인 예시인 피보나치

피보나치를 모른다면 클릭

피보나치 식: F( n ) = F( n-1 ) + F( n-2 )
F(5)를 구하고 싶다면, 위의 식에 따라 아래 그림처럼 할 수 있다.

1. 재귀 방법

이 방법에는 보관 방법이 빠져 있다.
만약 문제를 해결할 때 재귀의 수가 늘어날 수록 구한 값을 저장한 것이 없기에 구한 값을 또 구해야 하기 때문에 속도가 현저히 느려지게 된다.

def fib_naive(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    else:
        fib = fib_naive(n-1) + fib_naive(n-2)
        return fib
    
fib_naive(5)

2. Top-down 방법 and 보관 방법

이 방법은 구한 값을 보관해 놓는다.
재귀의 수가 늘어날 수록 1번 방법보다 훨씬 빠른 속도로 값을 구할 수 있게된다.

그러나, 이 방법은 위에서부터 아래로 구하기 때문에 구하려는 수가 피보나치 5가 아닌 피보나치 10000처럼 큰 수일 경우에는 오버플로우가 나타나게 된다.

그러면 어차피 맨 마지막 sub-problem에서부터 계산이 되어서 오는거라면 맨 마지막 sub-problem부터 계산게끔 만들어주면 되지 않을까? 하는 생각에 나온게 3번 방법이다.

fib_array = [0, 1]

def fib_recur_dp(n):
    if n < len(fib_array):
        return fib_array[n]
    else:
        fib = fib_recur_dp(n-1) + fib_recur_dp(n-2)
        fib_array.append(fib)
        return fib

fib_recur_dp(5)

3. Bottom-up 방법 and 보관 방법

이 방법은 가장 작은 sub-problem부터 해결하기 때문에 2번 방법에서 나온 오버플로우가 나타나지 않는다.
또한, 2번 방법의 속도보다 말도 안되게 빨라진다.

def fib_dp(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    
    fib_array = [0, 1]

    for i in range(2, n+1):
        num = fib_array[i-1] + fib_array[i-2]
        fib_array.append(num)
        
    return fib_array[n]

fib_dp(5)