다이나믹 프로그래밍, 파이썬 알고리즘
#파이썬 #다이나믹프로그래밍
다이나믹 프로그래밍
다이나믹 프로그래밍Dynamic programming 기법이란** 메모리 공간을 약간 더 사용해서 연산 속도를 비약적으로 증가시킬 수 있는 대표적인 방법이다. 다른 말로 **동적 계획법이라고도 부른다. 여기서 동적(Dynamic)이라는 뜻은 '프로그램이 실행되는 도중에'라는 뜻이다.
또한 다이나믹 프로그래밍이란 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다. 또한 다이나믹 프로그래밍에는 탑다운Top-Down 방식과 보텀업Bottom-Up 방식이 있다. 탑다운 방식은 '하향식'이라고도 하고, 보텀업 방식은 '상향식'이라고도 한다. 탑다운 방식에서는 메모이제이션Memoization** 기법이 사용된다. 메모이제이션은 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 의미하고, **캐싱Caching이라고도 한다. 반면 보텀업 방식에서는 'DP 테이블'이라는 결과 저장용 리스트가 쓰인다.
다이나믹 프로그래밍은 가능하다면 보텀업 방식 구현이 권장된다. 왜냐하면 시스템 상 재귀함수의 스택 크기가 한정되어 있어 탑다운 방식 구현이 어려울 수 있기 때문이다.
| 탑다운 | 보텀업 |
|---|---|
| 메모이제이션(=캐싱) | DP테이블 |
| 재귀함수 | 반복문 |
피보나치 수열을 '보텀업' 방식의 다이나믹 프로그래밍으로 풀어보겠다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# Python code
# 보텀업 다이나믹프로그래밍
# 피보나치 수열
# 앞서 계산된 결과를 저장하기 위한 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]
print(d[n]) # -> 218922995834555169026
피보나치 수열에 다이나믹 프로그래밍을 적용하면 시간 복잡도는 O(N)이다.
재귀함수로 푸는 탑다운 방식의 코드, 그리고 다양한 예제가 책에 수록되어 있으나 이 글에서는 다루지 않겠다. 나는 책에 수록된 예제를 몇 번 더 보고 복습하려고 한다. 탑다운 방식이나 보텀업 방식 모두 점화식이 쓰이는 점이 인상적이었다. 그리고 내 개인적으로는 재귀함수를 쓰는 탑다운 방식은 식은 더 복잡하지만 이해가 쉬웠고, 반복문을 쓰는 보텀업 방식은 더 권장되는 방법이고 코드도 더 간결하지만 구현이 쉽지 않아보였다. 익숙해져야 할 필요가 있다.
이 글의 내용이 많은 도움이 된다면 아래 책을 사서 읽어보고 공부하는 것을 추천한다.
이것이 취업을 위한 코딩 테스트다 with 파이썬
1
2
3
4
5
6
저자
나동빈
출판
한빛미디어
발매
2020.08.05.