#Dynaminc_programming #코딩공부

Dynamic programming을 위해서는 두 가지의 조건이 필요하다. 최적 부분 구조와 중복되는 부분 문제가 그 조건에 해당한다. 

- 조건 1) 먼저, 최적 부분 구조(optimal substructure)의 경우에는 부분 문제들의 최적을 답을 이용해서 원래 문제의 최적의 답을 구하는 방식이다. 

 출처 : Wikipedia, The Explaination of Dynamic Programming 

특정 시점의 최적값을 구하기 위해서 바로 전 시점의 최적값들의 비교를 통해서 현 시점의 최적값을 구하는 경우를 생각해보자. 

이전 시점의 최적값이 고정값인 경우도 있고(피보나치 수열의 경우) 혹은 여러 경우의 수에 따라서 값이 달라져 최적 부분 구조를 찾기 위해서 여러 조합을 후보로 생각해야 할 수도 있다. 

- 조건 2) 재귀 호출시 중복(overlapping recursive calls)일 경우, 재귀적 해법으로 풀면 같은 문제에 대한 재귀 호출이 심하게 중복되게 된다. 특정 문제가 중복되는지 아닌지의 여부는 특정 문제가 마치 트리 구조로 나누었을 때, 그 트리 구조에 속하는 값들이 중복되는 경우가 있는지 떠올려보자.

이에 해당하는 문제로는 피보나치 수열을 재귀함수를 이용해서 푸는 방법이 있다. (이와 다른 사례로는 합병정렬, 즉 반으로 쪼개서 정렬할 때 좌우 의 부분 문제가 서로 중복되지 않는 경우가 있다)

위의 두 가지 조건에 해당하는 경우 Dynamic Programming을 하며, 이 때 한 번 계산한 결과를 재활용하기 하며,

1) 기억하기(Momization) : 중복되는 식의 값은 메모리(cache)에 기억하여 나중에 이 값을 참고한다. 푸는 방식 자체는 재귀함수를 활용한다.

def filb_memo(n, cache):
	#부분문제로 나누지 않아도 되는 부분
    if n <3:
    	return 1
    #만약 이미 계산한 값이 있다면, cache에서 그 부분을 꺼낸다.     
    if n in cache:
    	return cache[n]
        
    cache[n] = fib_memo(n-1, cache) + fib_memo(n-2, cache)
    
    return cache[n]

def fib(n):
	#n번째 피보나치 수를 담는 사전이다.
    #{ ['n번째'] : n번째의 피보나치 수 ... } 로 구성된 딕셔너리다. 
    #dynamic programming 부분에서 cache값을 담는 부분은 아래의 딕셔너리에 해당한다. 
	fib_cache = {}
    
    return fib_memo(n, fib_cache)

 

2) 중복된 계산이 없도록 하는 방식(Tabulation)이 있다. 중복된 계산이 없도록 계산의 처음부분부터 단계적으로 진행하는 과정이다. 표에 차례대로 해당되는 값들을 입력한다고 하여, Tab라는 어근이 붙었다. programming을 하는데 있어서는 반복문을 이용해서 접근하게 된다. 

 

def fib_tab(n):
	# 각 index값이 n의 피보나치 수열값이라고 생각하면 된다.
    fib_table = [0,1,1]
    
    # 3부터 for문으로 dynamic programming하면 된다. 
    if n>3: 
    	for i in range(3, n+1): #n까지의 리스트를 차례대로 만드는 방법으로 한다. 
        	m= fib_table[i-2] + fib_table[i-1]
        	fib_table.append(m)
    
    return fib_table[n]     

 

단점 : Memoization에 비해서 불필요한 계산을 하게 될 수 있다.