[알고리즘] 다이나믹 프로그래밍
이것이 취업을 위한 코딩 테스트다. with 파이썬책을 참고하여 정리한 내용입니다.
✅ 다이나믹 프로그래밍(Dynamic Programming)
다이나믹 프로그래밍(Dynamic Programming)은 동적 계획법이라고도 표현하며, 메모리 공간을 더 사용해서 연산 속도를 비약적으로 증가시킬 수 있는 방법 중 대표적인 방법이다. 다이나믹 프로그래밍은 다음 조건을 만족할 때 사용할 수 있다.
- 큰 문제를 작은 문제로 나눌 수 있다.
- 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.
피보나치 수열은 이러한 조건을 만족하는 대표적인 문제이다. 피보나치 수열은 $a_{n+2} = f(a_{n+1}, a_n) = a_{n+1} + a_n$의 점화식을 가지는데, 이를 재귀 함수로 구현을 할 수 있다. 하지만 재귀 함수로 구현하는 경우, n이 커지면 커질수록 수행 시간이 기하급수적으로 늘어난다(시간 복잡도 : $(O2^n)$). 따라서 해당 문제를 메모이제이션(Memoization) 기법을 사용해서 해결할 수 있다.
메모이제이션(Memoization)은 다이나믹 프로그래밍을 구현하는 방법 중 하나로, 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 호출하면 메모한 결과를 가져오는 기법을 의미한다. 메모이제이션은 값을 저장하는 방법이므로 캐싱(Cashing)이라고도 한다. 리스트에 값을 저장하는 방식으로 구현할 수 있다.
✅ 시간 복잡도
다이나믹 프로그래밍의 시간 복잡도는 $O(N)$이다.
✔️ 피보나치 수열 재귀적 방법(Top-Down)(메모이제이션)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 한 번 계산된 결과를 메모이제이션(Memoization)하기 위한 리스트 초기화
d = [0] * 100
# 피보나치 함수(Fibonacci Function)를 재귀함수로 구현 (탑다운 다이나믹 프로그래밍)
def fibo(x):
# 종료 조건 (1 혹은 2일 때 1을 반환)
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]
이렇게 재귀 함수를 이용하여 다이나믹 프로그래밍을 구현하는 것을, 큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여 탑다운(Top-Down) 방식이라고 말한다. ‘하향식’이라고도 한다. 메모이제이션은 탑다운 방식에 국한되어 사용되는 용어다.
✔️ 피보나치 수열 반복적 방법(Bottom-Up)
1
2
3
4
5
6
7
8
9
10
11
# 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화
d = [0] * 100
# 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
d[1] = 1
d[2] = 1
n = 99
# 피보나치 함수(Fibonacci Function) 반복문으로 구현(바텀업 다이나믹 프로그래밍)
for i in range(3, n + 1):
d[i] = d[i - 1] + d[i - 2]
단순히 반복문을 이용하여 문제를 푸는 경우, 작은 문제부터 답을 도출한다고 하여 바텀업(Bottom-Up) 방식이라고 말한다. ‘상향식’이라고도 한다. 바텀업 방식에서 사용되는 결과 저장용 리스트는 ‘DP 테이블’이라고 부른다.
✅ 문제를 접근하는 방법
- 다이나믹 프로그래밍 유형임을 파악하기
- 특정한 문제를 완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래 걸리면 다이나믹 프로그래밍을 적용할 수 있는지, 해결하고자 하는 부분 문제들의 중복 여부를 확인해보자.
- 재귀 함수로 비효율적인 프로그래밍을 작성하고(탑다운), 메모이제이션을 적용할 수 있으면 코드를 개선해보자.
- 재귀 함수를 이용하는 탑다운 보다는 바텀업 방식으로 구현하는 것을 권장
- 재귀 함수의 스택 크기가 한정되어 있을 수 있다.