2022.03.19 TIL

동적 계획법(DP) 에 대해 알아보자

동적계획법 (Dynamic Programming)

• 입력의 크기가 작은 문제를 해결하여 이를 저장한 후, 해당 값을 통해 큰 문제를 해결하는 방식을 택한다.
• 알고리즘이 아닌 하나의 문제 해결 방식을 말한다.
• 동적계획법에의 방법론은 아래 2가지로 나뉜다.

  • 타뷸레이션(Tabulation)

    상향식 접근법으로 하위문제를 미리 계산하고 이를 이용해 상위 문제를 해결하는 방식이다. 일반적인 동적계획법은 타뷸레이션 방법론을 말한다.

  • 메모이제이션(Memorization)

    하향식 접근법으로 큰 문제를 쪼개 하위문제로 접근하여 문제를 해결한 후 해당 값을 저장한다. DP 에서 하위문제의 답은 매번 동일하기 때문에 저장한 값을 불러와 사용할 수 있다.

비슷한 방법으로 분할 정복 기법이 있다.
분할 정복은 문제를 잘게 쪼개서 각각을 풀이한 후 다시 합병하는 방식으로 하향식 접근법을 택한다.
이때 부분문제는 중복되지 않는다. (퀵 정렬, 그리디 등)

동적계획법의 대표적인 예시로 피보나치 수열이 있다.

피보나치 수열

• 재귀용법을 사용하여 구현한 피보나치 수열

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

• 동적계획법을 사용하여 구현한 피보나치 수열

def fibo_dp(n):
	# 저장공간을 먼저 만들어야 한다.
	dp = [0 for i in range(n + 1)]
	dp[0] = 0
	dp[1] = 1

	for idx in range(2, n + 1):
    	# 저장
		dp[idx] = dp[index - 1] + dp[index - 2]
	return dp[n]

출처
https://hongl.tistory.com/20