[알고리즘] 다이나믹 프로그래밍

정의

중복되는 연산을 줄이기 위하여 메모리 공간을 최대한 활용하여 연산 속도를 증가시키는 방법이다.

다이나믹 프로그래밍(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