! 이진 탐색까지 끝나고 이제 다이나믹 프로그래밍에 대해 공부한 내용을 정리해봤다.
1. 다이나믹 프로그래밍이란?
큰 문제를 작게 나누고, 같은 문제일 경우 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법
다이나믹 프로그래밍(Dynamic Programming)은 동적 계획법이라고 표현하기도 한다.
2가지 방식이 있는데 바로 탑다운과 보텀업이다. 추가적으로 이 책에서는 메모이제이션 기법까지 소개되어있다.
다이나믹 프로그래밍 기법 문제의 대표적인 예시는 바로 피보나치 수열이다.
피보나치 수열의 경우는 이전 두항의 합이 현재의 항으로 설정되는 수열이다.
예를 들면
1 1 2 3 5 8 13 21 ... 이런 식으로 이전 두 항 1+1 이 3번째 항 2가 되고,
다음 1 + 2가 4번째 항 3이되며 이런 방식으로 계속 반복이 이루어진다.
이 피보나치 수열의 경우 점화식으로 표현이 가능하다.
수학적 점화식을 프로그래밍으로 표현하려면 재귀 함수를 이용하면 된다.
- 피보나치 함수 코드
def fibo(x):
if x == 1 or x == 2:
return 1
return fibo(x - 1) + fibo(x - 2)
하지만 우리가 다음과 같이 피보나치 함수 코드를 사용할 경우 시간 복잡도에 심각한 문제가 발생하게 된다.
위의 그림을 보면 f(3)함수가 반복적으로 호출되는 것이 보인다. 이미 계산을 했음에도 호출 될 때마다 계산하는 것이다.
일반적으로 피보나치 함수의 시간복잡도는 O(2^n)으로 N=30일 경우 약 10억 가량의 연산을 수행해야한다. 시간이 너무 오래 걸린다!!
하지만 이러한 문제는 다이나믹 프로그래밍을 사용할 경우 효율적으로 해결이 가능하다.😁
하지만 항상 다이나믹 프로그래밍을 사용할 수는 없고, 조건을 만족할 때 사용이 가능하다.
-
큰 문제를 작은 문제로 나눌 수 있다.
-
작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
피보나치 수열은 이 조건에 해당하며, 다이나믹 프로그래밍의 메모이제이션 기법을 통해 다시 구현해보자.
- 메모제이션기법이란?
다이나믹 프로그래밍을 구현하는 방법 중에 한 종류로, 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출할 경우 메모한 결과를 그대로 가져오는 기법이다. 또 다른 말로 캐싱이라고도 한다.
우리는 리스트에 정보를 저장해서 이를 수행한다.
- 메모제이션 코드 구현
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]사실 큰 문제를 작게 나누는 방법은 우리가 앞서 배웠던 정렬 중 퀵 정렬도 비슷한 맥락이다. 이러한 알고리즘은 분할 정복(Divide and Conquer)로 분류된다.
그렇다면 다이나믹 프로그래밍과 분할 정복의 차이는 무엇이냐?
바로 다이나믹 프로그래밍은 문제들이 서로 영향을 미친다는 것이다.
퀵 정렬의 경우 한 번 기준 원소가 자리를 변경해서 결정될 경우 그 기준 원소의 위치는 다시 바뀌지 않고 그 피벗값을 다시 처리하는 부분 문제는 존재하지 않는다.
하지만 다이나믹 프로그래밍의 경우에는 한 번 해결했던 문제를 다시금 해결한다! 그렇기에 메모제이션 기법과 같이 리스트에 저장해 놓는 것이 아닌가
2. 탑다운 & 보텀업
앞서 말했듯이 다이나믹 프로그래밍에는 탑다운 방식과 보텀업 방식이 있는데
-
탑다운 방식(상향식) : 큰 문제를 해결하기 위해 작은 문제를 호출
재귀함수를 사용한다. -
보텀업 방식(하향식) : 작은 문제부터 차근차근 답을 도출
반복문을 사용한다.
우리가 위에 구현했던 방식은 탑다운 방식으로 보텀업 방식을 사용하면 다음과 같다.
d = [0] * 100
d[1] = 1
d[2] = 2
n = 99
for i in range(3, n+1):
d[i] = d[i-1] + d[i-2]
다이나믹 프로그래밍의 전형적인 형태는 보텀업 방식이다. 이때 사용되는 결과 저장용 리스트는(여기서는 d)에 경우 'DP 테이블'이라고 불린다.
메모제이션의 경우는 탑다운 방식에서 사용되는 표현이다.
이상 다이나믹 프로그래밍 정리 끝!
