728x90
반응형
정의
중복되는 연산을 줄이기 위하여 메모리 공간을 최대한 활용하여 연산 속도를 증가시키는 방법이다.
다이나믹 프로그래밍(dynamic programming)이라 표기하고 한국어 표기로는 "동적 계획법" 이라고 한다.
방식
- 탑다운 방식 (메모이제이션 활용)
- 보텀업 방식

구현
예시로 피보나치 수열이 있다
탑다운 방식
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]
d = [0] * 100
answer = fibo(99)
print('answer: {}'.format(answer)) # answer: 218922995834555169026
보텀업 방식
def fibo(x):
d = [0] * 100
d[1] = 1
d[2] = 1
n = 99
for i in range(3, n + 1):
d[i] = d[i - 1] + d[i - 2]
return d[x]
answer = fibo(99)
print('answer: {}'.format(answer)) # answer: 218922995834555169026
728x90
반응형