다이나믹 프로그래밍

다이나믹 프로그래밍(DP)이란?

최적의 해를 구하기에 시간이 매우 많이 필요하거나 메모리 공간이 매우 많이 필요한 문제를 해결하고자 하는 방법.

메모리를 적절히 사용하여 수행 시간을 비약적으로 증가시키는 방법.

이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 하는 방법.

일반적으로 Top-Down (메모이제이션), Bottom-Up 방식으로 구성한다.

 

동적계획법이라고도 부르며 다음과 같은 조건을 만족할 때 사용할 수 있다.

 

• 최적 부분 구조(Optimal Substructure)

    큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있을 때.

 

• 중복되는 부분 문제(Overlapping Subproblem)

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

 

대표적인 예시

 

피보나치 수열

An+2 = F(An+1,An) = An+1 + An

#재귀함수를 통한 피보나치
def recursive_fibonacci(x): 
	if x==1 or x == 2:
    	return 1
    else :
    	return recursvie_fibonacci(x-1)+recursive_fibonacci(x-2)

# 메모이제이션을 사용한 피보나치 (Top-Down)
def dp_fibonacci(x):
	dp = [0] * 100000
    dp[0],dp[1],dp[2] =1
    if x==1 or x == 2:
    	return 1
    if dp[x] != 0:
    	return dp[x]
    dp[x] = dp_fibonacci(x-1)+dp_fibonacci(x-2)
    return d[x]

#DP-table을 사용한 피보나치 (Bottom-Up)
def dp_fibonaccil(x):
	dp = [0]*100000
    dp[0],dp[1],dp[2]=1
    for i in range(3,len(dp)):
    	dp[i] = dp[i-2]+dp[i-1]
    return dp[x]

 

메모이제이션?

다이나믹 프로그래밍을 구현하는 방법 중 하나.

한 번 계산한 결과를 메모리 공간에 메모하는 기법.

• 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다.
• 값을 기록해 놓는다는 점에서 캐싱(Caching)이라고도 한다.