Dynamic Programming(동적 계획법)

✅ Dynamic Programming:

동적 계획법(DP, Dynamic Programming)은 큰 문제를 작은 문제로 나누고, 작은 문제들의 결과를 저장하여 같은 문제를 중복 계산하지 않도록 하는 알고리즘 기법입니다. 그리디 알고리즘 처럼 최적화 알고리즘이다.

동적계획법

 

DP 알고리즘 순서

문제를 DP로 풀 수 있는지 확인 

1. 최적 부분 구조 : 큰 문제의 최적해가 작은 문제들의 최적해로 구성될 수 있어야한다.

ex ) fib(n) = fib(n-1) + fib(n-2)

2. 중복되는 부분 문제 (Overlapping

 

 

---

 

#Top-Down 방식
def fibo_memo(n, memo={}):
    if n <= 1:
        return n

    if n not in memo:  # 값이 없으면 계산 후 저장
        memo[n] = fibo_memo(n - 1, memo) + fibo_memo(n - 2, memo)

    return memo[n]  # 저장된 값 반환

print(fibo_memo(5))  # 5


print(fibo_memo(10))  # 출력: 55

# Bottom-up 방식
def fibo2(n): 
    f = [0] * (n + 1)  # 크기가 (n+1)인 리스트를 생성하고 0으로 초기화
    f[0] = 0  # F(0) = 0
    f[1] = 1  # F(1) = 1

    for i in range(2, n + 1):  # 2부터 n까지 반복
        f[i] = f[i - 1] + f[i - 2]  # 점화식 적용: F(i) = F(i-1) + F(i-2)

    return f[n]  # F(n)을 반환
   
print(fibo2(10))  # 출력: 55

 

이렇게 작은 값부터 차례대로 구해 저장하며 F(n) 을 찾는다.