<aside> 🧨 DP하면 드라마나 포켓몬이 먼저 떠오를텐데(?), Dynamic Programming(동적 계획법)의 줄임말이다. DP를 쓰는 가장 큰 이유는 그 속도 때문이다. 더 빠른 속도로 연산이 가능하다니, 정확성에 더불어 효율성을 중시하는 알고리즘에 적합할 것처럼 들린다. 솔깃하다. 그렇다면 어디서, 어떻게 솔도를 최적화할 수 있는지 바로 알아보자.

</aside>

우리끼리니까 말하는건데, 필자가 이 글을 쓰는 이유는 필자가 DP에 취약하다고 생각하기 때문이다. 이 글을 쓰면서 DP의 포켓몬 마스터가 되겠다고 마음 먹었고(?), 이 글을 모두 읽은 사람도 DP의 마스터가 되길 바라는 마음으로 글을 써 보았다. 그러면 서론은 짧게 하고 바로 시작해 보자.

피보나치와 DP

DP를 설명할 때 굉장히 유명한 예시가 있다. 바로 피보나치 수 구하기이다.

int fibonacci(int n) {
		if (n < 2) return n;
		return fibonacci(n - 1) + fibonacci(n - 2);
}

우리가 잘 알고있는 피보나치 수열을 구해주는 간단한 함수이다. 재귀 호출(recursive calls)를 이용한 아주 깔끔한 코드이다.

자세히 들여다보면 이 코드에서 비효율적인 부분을 찾을 수 있을 것이다. 혹시 찾았는가? fibonacci(4) 를 호출한다고 생각해 보자. 그 안에서는 fibonacci(3) 과 fibonacci(2) 가 호출된다. 방금 나온 fibonacci(3) 을 또 들여다보면 fibonacci(2) 와 fibonacci(1) 을 호출한다. 여기까지만 봐도 fibonacci(2)를 벌써 두 번씩 호출하고 있는 것이 보인다! 심지어 fibonacci(1) 은 3번이나 호출되게 되는데, 지금은 숫자가 작지만, 이 숫자가 더 커지게 된다면 이 중복 계산들이 무지막지하게 많아지게 된다. 시간 복잡도가 $O(2^n)$ 에 달한다. 사용한 메모리(auxiliary space)는 $O(1)$이 되겠다.

주의: 아래에서 제공하는 두 방법은 DP를 설명하기 위한 예시일 뿐 가장 빨리 피보나치 수열을 구하는 방법이 아니다.

DP를 유도해보자

graph TD
  a(fib4) --> b(fib3)
	a --> c(fib2)

	b --> d(fib2)
	b --> e(fib1)
	c --> f(fib1)
	c --> g(fib0)
	
	d --> h(fib1)
	d --> i(fib0)

fibonacci(4) 쯤에서는 귀엽지만 fibonacci(10'000) 의 그래프에 얼마나 많은 중복이 있을지 상상해 보라. 끔찍하다.

fibonacci(2) 가 왼쪽 아래에 하나, 오른쪽에 하나 나오는 것을 시각적으로 확인할 수 있다. 우리 프로그래머들은 중복을 싫어한다. 없애보자.

graph
a[[fib2]] --> fib1
a --> fib0

이 부분만 따로 떼어내어서 어딘가에 저장하고 다시 사용한다면 우리의 fibonacci(4) 그래프를 중복 없이 더욱 깔끔하게 만들 수 있지 않을까? 이 부분만 코드로 바꾸면 이렇게 될 것이다 :

int fibonacci_2 = fibonacci(1) + fibonacci(0);

우리의 그래프는 다음과 같이 될 것이다 :

graph TD
  a(fib4) --> b(fib3)
	a --> c[[fib_2]]

	b --> d[[fib_2]]
	b --> e(fib1)

Table of Contents

피보나치와 DP

DP를 유도해보자