[이론] 다이나믹 프로그래밍

 

다이나믹 프로그래밍(=동적계획법)

- 배경) 컴퓨터는 연산 속도에 한계가 있고, 메모리 공간을 사용할 수 있는 데이터의 개수도 한정적

- 메모리 공간을 약간 더 사용하면 연산속도를 증가시킬 수 있는 방법

- 큰 문제를 작게 나누고, 같은 문제라면 한번 씩만 풀어 문제를 효율적으로 해결하는 알고리즘 

- 다이나믹 프로그래밍과 분할 정복의 차이점은 다이나믹 프로그래밍은 문제들이 서로 영향을 미치는 점

 

- 만족해야하는 조건

   1. 큰 문제를 작은 문제로 나눌 수 있다

   2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다

 

- 구현 방식

 1) TOP-DOWN(탑다운)방식  = 하향식 = 메모이제이션

 : 큰 문제를 해결하기 위해 작은 문제를 호출

 - 재귀함수를 이용하여 다이나믹 프로그래밍 소스코드를 작성하는 방법

 - 메모이제이션은 탑다운에 국한되어 사용하는 개념 

 - 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념, 다이나믹 프로그래밍과 별도의 개념이다

  - 한번 계산된 결과를 담아놓고 안쓸 수도 있다.

 

*메모이제이션 

: 다이나믹 프로그래밍을 구현하는 방법 중 한 종류로, 한 번 구현 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법 

 

 2) BOTTOM-UP(바텀업) = 상향식

 : 단순히 반복문을 이용하여 소스코드를 작성하는 경우 작은 문제부터 차근차근 답을 도출

- DP테이블: BOTTOM UP에서 사용되는 결과 저장용 리스트 

 

 

- 피보나치 수열

#피보나치 함수 소스코드
#
def fibo(x):
    if x==1 or x==2:
        return 1
    return fibo(x-1)+fibo(x-2)
print(fibo(6))
# 1 1 2 3 5 8 13 21

- 피보나치 수열 -TOP-DOWN 메모이제이션

#피보나치 수열 - 메모이제이션
dp=[0]*100
def fibo(x):
    if x==1 or x==2:
        return 1
    if dp[x] != 0:
        return dp[x]
    dp[x]=fibo(x-1)+fibo(x-2)
    return dp[x]
print(fibo(99))

- 피보나치 수열 - Bottom-up 

#피보나치 수열 - bottom up (반복문)
dp=[0]*100 #DP테이블

dp[1]=1
dp[2]=1
n=99

for i in range(3,n+1):
    dp[i]=dp[i-1]+dp[i-2]

print(dp[n])

 

*문제풀이

1. 유형 파악하기

: 특정한 문제를 완전탐색 알고리즘으로 접근 했을 때 시간이 매우 오래 걸리면 다이나믹 프로그래밍을 적용할 수 있는지 해결하고자 하는 문제들의 중복여부 확인

2. 일단 재귀함수로 비효율적인 프로그램을 작성후 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면(=상향식=메모이제이션) 코드 개선하기

3. 가능하면 Top-down보다는 Bottom-up을 구현하기

- 시스템상 재귀함수의 스택 크기가 한정되어 있을 수 있기 때문