[알고리즘] DP (동적계획법)

DP(Dynamic Programming) 란?

• 입력 크기가 작은 부분문제들을 해결하고 난 후, 이것을 활용하여 큰 크기의 부분문제를 해결, 최종적으로 전체문제를 해결
• 상향식 접근법임 - 가장 최하위 해답을 구한 후, 이를 이용해서 상위 문제를 풀어가는 방식 
• Memorization 기법을 사용 - 이전에 계산한 값을 저장하여, 다시 계산하지 않도록 해서 전체 실행속도 빠르게

 

재귀 vs 동적계획법

n을 입력받았을 때 피보나치 수열로 결과값을 출력하시오

#재귀호출

def fibo(num):
	if num <= 1:
    	return num
    return fibo(num - 1) + fibo(num - 2)

 

#동적계획법

def fibo_dp(num):
	cache = [0 for index in range(num + 1)]
    cache[0] = 0
    cache[1] = 1
    
    for index in range(2, num + 1):
    	cache[index] = cache[index - 1] + cache[index - 2]
    
    return cache[num]