[Algorithm] Dynamic Programming(1) - Warm Up

🤔Dynamic Programming

다이나믹 프로그래밍이란 큰 문제를 작은문제로 나누어 문제를 해결하는 것을 말합니다.

 

다이나믹 프로그래밍 알고리즘을 이용하는 다양한 알고리즘에 대해 알아보겠습니다.

 

이번 시간에는 다이나믹 프로그래밍이 어떤 것인가에 대해서 알아보도록 하겠습니다.

 

 

 

 

 

 

 

 

 

 

 

 

🔎  피보나치 수열

컴퓨터를 배운 사람이라면 한 번쯤 풀어봤을 피보나치 수열 문제입니다. (피보나치 수열을 잘 모르시는 분은 해당 링크를 참고하시길 바랍니다.)

 

피보나치 수열은 Recursion을 이용하여 해결할 수 있습니다.

 

👉 피보나치 수열 수도코드

fib(n):
	if(n == 0)
    	return 0
    if(n == 1)
    	return 1
    return fib(n-1) + fib(n-2)

 

 

 

 

해당 알고리즘의 시간 복잡도는 subproblem의 정의를 통해 해결 할 수 있습니다.

 

 

 

Subproblem 정의

$T(n)$을 위의 $fib(n)$의 답을 얻을 때 까지 필요한 총 addition의 횟수라고 하겠습니다.

 

그렇다면 아래와 같은 recurrence relation을 얻을 수 있습니다.

 

$$T(n) = T(n-1) + T(n-2) + 1,\; T(0) = T(1) = 0$$

 

해당 recurrennce relation을 해결하면 $T(n) ~ 1.618^n$을 얻을 수 있습니다.

 

매우 느린 시간 복잡도를 가진다는 것을 알 수 있습니다.

 

이는 아래의 recursion tree를 통해 이유를 확인 할 수 있습니다.

 

 

 

 

 

recursion tree에서 $F_3$을 확인해보겠습니다.

 

재귀적 호출을 진행하면서 $F_3$가 총 5번 호출되는 것을 알 수 있습니다.

 

즉, 같은 함수를 재귀를 진행하는 동안 반복해서 호출해야 되기 때문에 느린 시간 복잡도를 가지는 것입니다.

 

이를 해결하기 위해서는 재귀 호출을 진행하며 결과물이 나올 때마다 저장한 뒤, 이후에 같은 함수를 호출하게 된다면 저장했던 결과를 사용하면 됩니다.

 

 

 

👉 저장을 이용하여 해결한 피보나치 수열 수도코드

global F[0..n] = {0, 1, null, ... null};
Fib(n):
	if (n == 0)
		return 0
	if (n == 1)
		return 1
	if F[n] == null
		F[n] = Fib(n-1) + Fib(n-2)
	return F[n]

 

 

 

이와 같이 재귀함수의 중간 결과를 저장하는 기법을 memoization이라고 합니다.

 

또한 recursion과 memoization을 사용하여 문제를 해결하는 기법을 dynamic programming이라고 합니다.

 

해당 수도코드의 time complexity를 계산해보겠습니다.

 

F[n]의 값이 null일 때만 덧셈을 한 번 수행하면 해당 값이 결정되므로 총 n번의 덧셈을 진행하게 됩니다.

 

저장 또한 총 n번 진행하기 때문에 총 time complexity는 $O(n)$이 됩니다.

 

 

이를 recrsion tree와 저장된 배열로 확인하면 아래와 같습니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

🔎 Dynamic Programming의 순서

Dynamic Programming을 통해 문제를 해결하는 방법은 아래의 순서를 거치면 됩니다.

 

 

 

 

Dynamic programming 으로 문제를 해결하는 방법

1. 문제를 정확하게 정의합니다.
2. 정의된 문제에 대한 subproblem 을 정의한 뒤 (앞 예시에서는 $subproblem = F_n’ \,(n’ < n)$ 구하기가 subproblem), subproblem 을 이용한 recurrence relation 을 세웁니다.
3. Memoizaion 을 이용하여 recurrence relation 계산합니다.
  - 중간 결과물들을 저장할 data structure를 고릅니다. (보통 n 차원 array 사용.)
  - Subproblem 들 간의 dependency를 확인합니다. (예 : $F_n$ 을 구하려면 어떤 subproblem의 답들을 계산해 놓아야 하는가?) 
  - Dependency 에 기반하여 subproblem 들의 답을 구하는 순서를 정합니다..
4. Time complexity를 분석하고 알고리즘을 작성합니다.

 

 

 

 

 

다음 포스팅에서는 여러가지 예시를 통해 DP를 더 알아보도록 하겠습니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

🔎 Reference

https://galid1.tistory.com/507

알고리즘 - Dynamic Programming(동적프로그래밍)이란?