Dynamic Programming(다이나믹 프로그래밍)

설명

필요한 계산 값을 저장해두었다가 재사용 하는 알고리즘 설계 기법이다.

큰 문제를 한번에 해결하기 어려울 때, 여러개의 작은 문제로 나누어 푸는 ‘분할 정복’ 알고리즘이 있다. 이때 동일한 작은 문제 들이 반복적으로 계산 되는 경우가 생길 수 있다. 그 문제를 매번 재계산 하지 않고 값을 저장했다가 재사용하는 기법이 바로 다이나믹 프로그래밍이다. 메모리 공간을 약간 더 사용하여 시간을 획기적으로 줄일 수 있는 방법이다.

여담이지만 다이나믹 프로그래밍의 Dynamic은 동적 할당(Dynamic Allocation)의 Dynamic과 아무런 관계가 없다.

동적할당에서 Dynamic은 ‘프로그램이 실행되는 도중’에라는 의미이지만 다이나믹 프로그래밍에서 Dynamic은 고안자인 벨만(Richard E. Bellman)이 연구소에서 펀딩을 받으려고 멋있는 단어를 선택했다고 한다. Programming이란 단어는 최적화 연구 분야에서 최적의 프로그램을 찾아낸다는 의미로 사용된다.

다이나믹 프로그래밍은 다음과 같은 조건을 만족할때 사용할 수 있다.

1. 최적 부분 구조

큰 문제를 작은 문제를 나눌 수 있다. 이러한 작은 문제의 답을 모아 큰 문제를 해결할 수 있다.

2. 중복된 하위 문제

동일한 작은 문제를 반복적으로 해결해야 한다.

예시 : 피보나치 수열

다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시가 바로 피보나치 수열이다.

피보나치 수열은 현재 항을 계산하기 위해 이전 두항의 합을 구해야한다. 이를 표현하기 위해 다음과 같은 점화식을 사용한다.

이를 재귀함수를 사용하여 코드로 구현하게 되면 다음과 같다.

def fibo(x):
    if x == 1 or x == 2:
        return 1
    return fibo(x-1) + fibo(x-2)

해당 코드는 O(2^N)의 시간복잡도를 가지게 되어 N이 증가함에 따라 수행시간이 기하급수적으로 늘어난다. 예를 들어 N=30이면 약 10억 가량의 연산을 수행해야한다. f(5)일때 호출과정을 그림으로 표현하면 다음과 같다.

그림을 통해 동일한 함수 가 반복적으로 호출되는 것을 알 수 있다. 이미 한번 계산했지만 계속 호출할때마다 계산을 하는 것이다. 그림에서 fib(1)은 총 5번, fib(2)는 총 3번 호출되어 계산되었다. 다이나믹 프로그래밍은 이러한 반복적인 계산 을 방지해주는 알고리즘 설계 기법이다.

Topdown

탑다운 방식은 메모이제이션을 사용하여 다이나믹 프로그래밍을 구현하는 방식 중 하나이다.

메모이제이션(memoiztion)이란 한번 구한 계산 결과를 메모리 공간에 메모해두고, 같은 식을 다시 호출하면 메모한 결과 그대로 가져오는 기법을 말한다. 탑다운 방식은 큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여 하향식이라고도 불린다. 이러한 탑다운방식은 재귀함수를 이용하여 구현할 수 있다.

 
 # 한번 계산된 결과를 메모이제이션하기 위한 리스트
 memo = [0]*100

 # 피보나치 수열을 재귀함수로 구현(topdown)
 def fibo(x) :
     
     if x == 1 or x == 2 :
         return
    
     #이미 계산한 적있는 문제라면 그대로 반환

     if memo[x] != 0:
         return memo[x]
    
     memo[x] = fibo(x-1) + fibo(x-2)
     return memo[x]

Bottom-up

보텀업 방식은 타블레이션(tabulation)을 사용하여 다이나믹 프로그래밍을 구현하는 방식 중 하나이다.

타블레이션(tabulation)이란 하위 문제부터 천천히 해결하면서 더 큰 문제를 해결하는 기법을 말한다. 타블레이션이라고 부르는 이유는 작은 문제부터 큰 문제까지 하나하나 테이블을 채워간다는 의미 때문이다. 보텀업 방식은 하위 문제부터 시작해서 더 큰 문제를 해결해 나가기 때문에 상향식이라고도 한다. 다이나믹 프로그래밍의 전형적인 형태는 바로 이 보텀업 방식이다. 보텀업방식은 반복문을 이용하여 구현할 수 있다.

dp = [0]*100


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])

참조 블로그

나중에 되면 잊어버릴까봐 그대로 내용을 가져왔습니다. 감사합니다. https://doing7.tistory.com/75