다이나믹 프로그래밍 #메모이제이션 #피보나치수열 #탑다운 #보텀업

 

 

📌 다이나믹 프로그래밍의 배경: 중복되는 연산을 줄이자.

우리는 알고리즘을 설계할 때 연산 속도와 메모리 공간을 효율적으로 활용해야 한다.

하지만 어떤 문제에서는 메모리 공간을 조금 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법이 있다.

이 방법이 바로 다이나믹 프로그래밍 (Dynamic Programming, DP) 기법이다.

다이나믹 프로그래밍은 중복되는 연산을 줄여서 문제를 효율적으로 해결하는 알고리즘이다.

---

📌 피보나치 수열: 재귀 함수 풀이

피보나치 수열은 다음과 같이 정의할 수 있다:

$a_{n} = a_{n-1} + a_{n-2} , a_{1} = 1, a_{2} = 1$

 

 

재귀를 이용한 코드 예시

import time

def fibo(x):
    if x == 1 or x == 2:
        return 1
    return fibo(x - 1) + fibo(x - 2)

# 실행 시간 측정
n = 30 
start_time = time.time()  
result = fibo(n)  
end_time = time.time()  

print(f"Fibo({n}) = {result}")
print(f"실행 시간: {end_time - start_time:.6f}초")

# Fibo(30) = 832040
# 실행 시간: 0.094034초

 

 

문제점

이 방식의 문제는 중복된 계산이 많다는 것이다.

이미 한 번 계산했지만, 계속 호출할 때 마다 계산하는 것이다. 

예를 들어, fibo(6)을 계산하는 과정에서 fibo(3)은 세 번 계산된다. 이러한 중복 계산은 시간이 급격하게 증가하게 만든다.

위 코드의 시간 복잡도는 $O(2^N)$이다. 예를 들어, N=30일 때 약 10억 번의 연산이 필요하다.

 

재귀 함수: fibo(6) 호출

 

 

피보나치 수열의 점화식을 재귀 함수를 사용해 만들 수는 있지만, 단순히 매번 계산하도록 하면 문제를 효율적으로 해결할 수 없다. 

---

📌 피보나치 수열: 다이나믹 프로그래밍 (메모이제이션)

이러한 문제는 다이나믹 프로그래밍을 사용하면 효율적으로 해결할 수 있다. 

 

다이나믹 프로그래밍은 다음 조건을 만족할 때 사용할 수 있다. 

1. 큰 문제를 작은 문제로 나눌 수 있다.

2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

 

피보나치 수열을 메모이제이션(Memoization) 기법을 사용해서 해결해보자. 

" 이미 계산한 결과를 저장하여 중복 계산을 줄이자!" 이를 메모이제이션 기법이라고 한다. 

import time

d = [0] * 100

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]

# 실행 시간 측정
n = 30 
start_time = time.time()  
result = fibo(n)  
end_time = time.time()  

print(f"Fibo({n}) = {result}")
print(f"실행 시간: {end_time - start_time:.6f}초")

Fibo(30) = 832040
실행 시간: 0.000008초

 

• 시간: 0.094034초 → 0.000008초로 줄어듦.
• 시간 복잡도: $O(2^N)$ → $O(N)$.
• 한 번 계산한 fibo(n) 값을 리스트에 저장하고, 같은 값이 다시 필요할 때 리스트에서 가져오기 때문에 실행 시간 줄어듦.

f(6) 해법을 다시 메모이제이션 기법을 이용하여 그려보면 6번째 피보나치 수를 호출할 때는 다음 그림처럼 색칠된 노드만 방문하게 된다.  나머지 점선 노드는 호출하더라도 따로 계산하지 않고 리스트에서 값을 가져오거나 바로 1을 반환하기 때문이다. 

메모이제이션 기법으로 fibo(6) 호출 시 실제 계산 노드(파란 노드), 리스트에서 값을 가져오는 노드(점선 노드)

 

 

---

📌  다이나믹 프로그래밍: 탑다운(Top-Down) vs 보텀업(Bottom-Up)

탑 다운 방식: 재귀 + 메모이제이션

• 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식.
• 한 번 계산된 결과를 메모이제이션하여 중복 계산을 방지. 

하지만 재귀 호출의 오버헤드(메모리 사용량) 문제가 발생할 수 있으므로, 아래의 보텀업 방식을 추천한다. 

 

보텀업 방식: 반복문 사용 

• 작은 문제부터 차근차근 해결하여 DP 테이블을 채우는 방식.
• 재귀 호출 없이 반복문으로 구현하여 메모리 절약 가능.

import time

d = [0] * 100
d[1] = 1
d[2]
n = 30

start_time = time.time()  

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

end_time = time.time()  

print(f"Fibo({n}) = {d[n]}")
print(f"실행 시간: {end_time - start_time:.6f}초")

# Fibo(30) = 317811
# 실행 시간: 0.000007초

 

 

 

 

• 보텀업 방식은 재귀 호출을 사용하지 않으므로 더 안정적이다. 
• 시스템의 호출 스택 크기의 영향을 받지 않는다.