다이나믹 프로그래밍

이미 계산된 결과(작은 문제)는 별도의 메모리 공간에 저장해 둠으로써 중복 연산을 줄여 수행시간을 줄일 수 있다

 

다이나믹 프로그래밍을 사용할 수 있는 조건

1. 최적 부분 구조: 큰 문제를 작은 문제로 나눌 수 있고, 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다

2. 중복되는 부분 문제: 동일한 작은 문제를 반복적으로 해결해야 함

 

다이나믹 프로그래밍 방식으로는 

1. 탑다운(메모이제이션)

2. 보텀업

두가지가 있다.

 

탑다운 방식은 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식이고,

보텀업 방식은 단순히 반복문을 이용하여 작은 문제부터 차근차근 답을 도출하는 방식이다.

 

 

탑다운 방식은 보통 재귀함수를 이용하는데, 재귀함수 깊이 제한 때문에 문제가 생길 수 있으므로 보텀업 방식을 권장한다.

고한다..

 

 

예시로 피보나치 수열 소스코드를 보자

#단순 재귀 소스코드
def fibo(x):
    if x==1 or x==2:
        return 1
    return fibo(x-1)+fibo(x-2)

print(fibo(4))
#실행은 되나 숫자가 커지면 계산시간이 기하급수적으로 커짐

다이나믹 프로그래밍을 사용하지 않은 피보나치수열 예시코드다. 

시간복잡도가 O(2^N)으로 N이 100정도가 되면... 평생 기다려야한다.

 

 

이것을 탑다운 방식 다이나믹 프로그래밍으로 하면

 

#탑다운(메모이제이션)방식.(하향식) - 이전에 계산된 결과를 일시적으로 기록해 놓는 것
d=[0]*100 #한번 계산한 값은 이 리스트에 저장할 것임. DP테이블
def fibo2(x):
    if x==1 or x==2:
        return 1
    if d[x]!=0: #계산 된 적 있을 때
        return d[x]
    
    #계산된 적이 없는 문제라면 점화식에 따라 계산하여 d[x]에 기록하고 d[x]반환
    d[x]=fibo2(x-1)+fibo2(x-2)
    return d[x]

print(fibo2(99))

대략 이렇게 된다.

d 라는 일차원리스트를 0으로 초기화 해두고, 

계산한 적 없는 문제면 계산하여 d[x]에 저장해두고 d[x]를 반환,

계산한 적 있는 문제라면 d[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]

print(d[n])

보텀업 방식.

반복문을 이용하여 d[3]부터 d[99]까지 차근차근 값을 채워 나간 후, 

d[n]을 출력한다.