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

오늘은 다이나믹 프로그래밍에 대해서 공부해보겠습니다. 1학기 때에 산업공학 전공 수업인 경영과학에서 다이나믹 프로그래밍 방법을 이용해서 최적화 문제들을 풀었었는데 매우 재미있게 공부했습니다v_v

다이나믹 프로그래밍이 무엇인지 차근차근 알아봅시다.

💡 다이나믹 프로그래밍이란?

DP란 입력 크기가 작은 부분 문제들의 해를 이용해서, 큰 부분의 문제를 해결하여 최종적으로 전체 문제를 해결하는 알고리즘을 말합니다. 상향식Bottom-up 접근법으로, 가장 최하위 해답을 구한 후, 이를 저장하고 그 값으로 상위 문제를 풀어가는 방식으로 memoization 기법을 이용합니다.

memoization 기법이란, 주어진 입력값에 대한 결과를 저장해 놓음으로써 같은 입력값이 또다시 들어왔을 때, 저장해놓은 값을 사용하여 함수가 한 번만 실행되는 것을 보장하는 기법입니다.

일반적으로 경영과학의 관점에서는 연속된 상호 관련된 의사 결정을 해야할 때 사용되는 기법입니다. 예를들어, 일반적으로 1월의 생산량은 2월의 생산량에 영향을 미치고, 2월의 생산량은 3월의 생산량에 영향을 미치기 때문에 매 달의 최적 생산량을 결정할 때 DP를 사용합니다.

 

💡 피보나치

DP를 활용하는 가장 대표적인 문제는 피보나치 수열을 만드는 문제입니다. 피보나치 수열은 재귀함수에서도 대표적인 문제에 해당하는데요, 두 방법으로 모두 이용하여 어떤 차이점이 있는지 비교해보도록 하겠습니다.

https://en.wikibooks.org/wiki/File:Algorithms-F6CallTree.png

피보나치가 재귀함수와 DP를 사용할 수 밖에 없는 이유는 위 그림에서 보실 수있습니다. f(4)를 구하기 위해서는 f(2)와 f(3)의 값이 필요하고, 또 f(2)를 계산하기 위해서는 f(0)과 f(1)의 값이 필요하고 f(3)을 계산하기 위해서는 f(1)과 f(2)가 필요하고 f(2)는 또 f(0)과 f(1)이 필요합니다.  

먼저 재귀함수로 구현해보도록 하겠습니다.

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

return으로 자기자신 함수를 부름으로써 간단히 작성할 수 있습니다.

하지만 위 코드으 시간 복잡도를 계산하여 보면 $O(2^n)$입니다. 즉, $n$이 커질 수록 시간복잡도가 기하급수적으로 늘어난다는 의미입니다. 이유는 $f(6)$를 계산하기 위해서는 $f(3)$의 값이 3번 필요한데, 그 값이 필요할 때마다 매번 재귀적으로 계산하기 때문입니다. 

 

하지만, memoization 기법을 사용하는 DP로 피보나치를 구하는 프로그램을 짠다면 시간복잡도를 훨씬 줄일 수 있습니다.

def fibonacci_dp(num):
	dp = [0 for _ in range(num + 1)]
	dp[1] = 1

	for idx in range(2, num + 1):
		dp[index] = dp[index - 1] + dp[index - 2]
	return dp[num]

dp라는 리스트에 앞서 계산해 놓은 값들을 저장해 놓기 때문에 재귀함수로 구현한 코드처럼 반복적으로 계산할 필요가 없습니다. 즉, 한 번 계산한 값은 다시 함수를 실행할 필요가 없는 것이지요! 따라서 위 코드의 시간복잡도는 $O(n)$으로 매우 단축됩니다.

 

다이나믹 프로그래밍의 코드 작성 패턴은 대부분 비슷합니다.

1. 입력값에 따른 빈 리스트 만들기

2. 초기값 설정

3. 점화식 기반으로 계산 값 적용

4. 특정 입력값에 따른 계산값을 리스트에서 출력

 

여기서 가장 핵심이 되는 부분은 점화식을 세우는 부분으로, DP알고리즘을 짤 때에는 가장 적은 경우의 수부터 계산을 해본 후에 패턴을 찾아서 점화식만 세운다면 코드 자체는 매우 간결하게 작성할 수 있습니다.

 

💡 다이나믹 프로그래밍 백준 문제

BAEKJOON #11726) 2xn 타일링 | DP | Python

BAEKJOON #9461) 파도반 수열 | DP | Python

BAEKJOON #1904) 01타일 | DP(다이나믹 프로그래밍) | Python