동적 계획법
동적 계획법이란 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 이용해 다시 큰 문제를 해결할 때 사용하는 것이다.
❗분할 정복(Divide and Conquer)와의 차이
분할 정복은 큰 문제를 해결하기 어려워 작은 문제로 나누어 푸는 방법이다 동적프로그래밍은 작은 부분문제들이 반복되는 것을 이용해 풀어나가는 방법이다. 병합 정렬은 분할 정복, 피보나치 수열은 동적 프로그래밍으로 해결이 가능하다.
동적 계획법 사용 조건
- 작은 문제들이 반복된다
동적 계획법은 기본적으로 문제를 나누고 그 문제의 결과 값을 다시 활용해서 전체 답을 구한다. 동일한 작은 문제들이 반복해서 나타나는 경우에 사용이 가능하다. 즉, 부분 문제의 결과를 저장하여 재계산하지 않게 하는데, 부분 문제가 반복적으로 나타나지 않는다면 사용할 수 없다. - 같은 문제는 항상 정답이 같다
이 두 조건이 만족해야 동적 계획법을 사용할 수 있다.
Memoization
동적 프로그래밍에서 작은 문제들이 반복되고 이 작은 문제들의 결과값이 항상 같다. 이 점을 이용하여 한번 계산한 작은 문제를 저장해놓고 다시 사용한다. 이것을 memoization라고 하고 동적 계획법의 핵심이 되는 기술이다.
구현
-
Bottom-Up 방식
아래에서부터 계산을 수행하고 누적시켜서 전체 큰 문제를 해결하는 방식이다. 주로 반복문을 이용하며 해결은 용이하지만 가독성이 떨어진다.예)피보나치 수열
f = [0] * 100
#첫 번째 피보나치 수와 두 번째 피보나치 수는 1
f[1] = 1
f[2] = 1
n = 99
#피보나치 함수(Fibonacci Function) 반복문으로 구현(보텀업 다이나믹 프로그래밍)
for i in range(3, n + 1):
f[i] = f[i - 1] + f[i - 2]
print(f[n])-
Top-Down 방식
큰 문제를 풀다가 풀리지 않은 작은 문제가 있다면 그때 해결하는 방식히다. 주로 재귀 방식으로 하며 가독성이 좋지만, 코드 작성이 힘들다.예)피보나치 수열
# 한 번 계산된 결과를 메모이제이션(Memoization)하기 위한 리스트 초기화
f = [0] * 100
# 피보나치 함수(Fibonacci Function)를 재귀함수로 구현 (탑다운 다이나믹 프로그래밍)
def fibo(x):
# 종료 조건(1 혹은 2일 때 1을 반환)
if x == 1 or x == 2:
return 1
# 이미 계산한 적 있는 문제라면 그대로 반환
if f[x] != 0:
return f[x]
# 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환
f[x] = fibo(x - 1) + fibo(x - 2)
return f[x]
print(fibo(99))