[개념 학습 및 정리] 동적 계획법

1. 동적 계획법

1) 동적 계획법과 분할 정복법

동적 계획법은 부분 문제를 해결한 결과를 이용하여 전체 문제를 해결하는 방법이다. 대표적으로 피보나치 수를 구하는 문제가 있다. 처음이라면 분할 정복법과 혼동될 수 있지만, 피보나치 수를 구하기 위해 다음과 같이 작성한 재귀함수를 예시를 든다면 차이를 확인할 수 있다.

static int fibonacci(int n) {
   if(n == 0 || n == 1) return n;
   return fibonacci(n-1) + fibonacci(n-2);
}

예를 들어 4를 넣어본다면, 중복된 계산을 계속 진행함을 확인할 수 있다.

• f(4) = f(3) + f(2)
• f(4) = ( f(2) + f(1) ) + f(2)
• f(4) = ( ( f(1) + f(0) ) + f(1) ) + f(2)
• ...

 

즉, 피보나치 수 구하기 문제는 소문제를 여러번 계산하는 일이 발생하며, 문제를 독립적으로 나누지 않았기 때문에 분할 정복법을 이용한 풀이를 적용해서는 안된다.

 

이 문제는 작은 "나"를 해결한 결과를 계속해서 사용을 한다는 점으로, 모든 풀이를 먼저 구하자는 아이디어를 생각해낼 수 있다. 예를 들어, f(6)를 구하기 위해 f(1), f(2), f(3), f(4), f(5)를 차례대로 구하여 사용하는 방법을 이용할 수 있다.

 

이러한 과정에서 분할 정복법은 Top-down 방식, 동적 계획법은 Bottom-up 방식임을 확인할 수 있다.

2) 동적 계획법 문제 풀이 순서

• 어떤 값을 구하는지에 대한 정의 (부분 문제 정의)
• 전체를 풀기 위해 부분은 풀려있다고 가정하고 식 구성 (점화식)
• 문제 해결

 

 

 

2. 피보나치 수 구하기

F(n) = F(n-1) + F(n-2)

 

부분 문제 정의) F(i)의 값을 찾는 문제

 

점화식) 부분 문제 혹은 소문제(F(i-1), F(i-2))는 다 풀려있다는 가정

F(i) = F(i-1) + F(i-2)

 

문제 해결) F(0), F(1) 기저조건을 이용

F(0)	F(1)	F(2)	F(3)	F(4)	F(5)	F(6)
1	1	2	3	5	8	13

 

 

 

3. 블럭 채우기

2 x n의 상자를 2 x 1의 블럭으로 채우는 경우의 수를 구하는 방법

블럭 채우기

부분 문제 정의)

전체 경우를 어떻게 나눌 것인지 정의를 한다. 예를 들어, 2 x 4의 상자일 때, 마지막 블럭의 모양을 나누어 정의를 한다면, 2 x 3을 채우는 경우의 수와 2 x 2를 채우는 경우의 수를 알면 해결할 수 있다는 것을 알 수 있다.

 

• T(2) = 2 x 2의 상자를 채우는 경우의 수 1
• T(3) = 2 x 3의 상자를 채우는 경우의 수 3
• T(i) = 2 x i의 상자를 채우는 경우의 수

 

부분 문제 정의

 

점화식)

• 마지막 블럭의 모양이 세로일 경우 2 x (i-1)의 상자를 채우는 경우의 수는 T(i-1)
• 마지막 블럭의 모양이 가로일 경우 2 x (i-2)의 상자를 채우는 경우의 수는 T(i-2)
• 즉, T(i) = T(i-1) + T(i-2)로 피보나치 수열 구하는 문제

 

문제 해결) T(1), T(2)의 기저조건을 사용 (T(0)는 2 x 0인 경우이기에 사용 하지 못함)

T(0)	T(1)	T(2)	T(3)	T(4)	T(5)	T(6)
	1	2	3	5	8	13

 

 

 

4. 숫자 만들기

1부터 m까지의 숫자를 더하여 n을 만드는 경우의 수를 구하는 방법

 

부분 문제 정의)

예를 들어, n = 5, m = 3일 때의 모든 경우의 수는 다음과 같다.

1 + 1 + 1 + 1 + 1 1 + 1 + 1 + 2 1 + 1 + 2 + 1 1 + 2 + 1 + 1 2 + 1 + 1 + 1 1 + 2 + 2 2 + 1 + 2 2 + 2 + 1 1 + 1 + 3 1 + 3 + 1 3 + 1 + 1 2 + 3 3 + 2

모든 경우의 수를 마지막이 각각 1, 2, 3으로 끝나는 경우로 분리한 결과, 다음과 같이 표현할 수 있다.

• 마지막이 1인 경우의 수 = 앞이 4를 만드는 경우의 수 = 7
• 마지막이 2인 경우의 수 = 앞이 3를 만드는 경우의 수 = 4
• 마지막이 3인 경우의 수 = 앞이 2를 만드는 경우의 수 = 2

 

1 + 1 + 1 + 1 + 1 1 + 1 + 2 + 1 1 + 2 + 1 + 1 2 + 1 + 1 + 1 2 + 2 + 1 1 + 3 + 1 3 + 1 + 1

1 + 1 + 1 + 2 1 + 2 + 2 2 + 1 + 2 3 + 2

1 + 1 + 3 2 + 3

 

점화식)

n과 m이 주어졌을 때 모든 경우의 수(T(i))를 구하는 방법은 다음과 같다.

• ... + 1 = (n-1)을 만드는 경우의 수
• ... + 2 = (n-2)을 만드는 경우의 수
• ... + 3 = (n-3)을 만드는 경우의 수
• ...
• ... + m = (n-m)을 만드는 경우의 수
• T(i) = T(i-1) + T(i-2) + ... + T(i-m)

 

문제 해결)

m = 3일 때, 앞의 3개의 값이 필요하기 때문에 왼쪽에서 오른쪽으로 값을 채워야 한다. 단 T(1), T(2), T(3)을 직접 구해주어야 한다.

 

T(0)	T(1)	T(2)	T(3)	T(4)	T(5)	T(6)	T(7)
	1	2	4	7	13	24	44

 

 

 

5. 연속 부분 최대합

연속된 부분을 선택했을 때, 그 최대 합을 출력하는 방법

• 완전탐색법은 O(n^3)
• 분할 정복법은 O(n logn)

 

1

2

-4

5

3

-2

9

10

 

부분 문제 정의)

부분 문제 정의

점화식)

• T(i)는 i번째 숫자를 오른쪽 끝으로 하는 연속 부분 최대합
• T(5) = (T(4) + 5번째 숫자, 5번째 숫자) 중 최대
• T(i) = max( T(i-1) + Data(i), Data(i) )

 

문제 해결) 더한게 큰가 혼자있는게 큰가를 생각

T(0)	T(1)	T(2)	T(3)	T(4)	T(5)	T(6)	T(7)
1	3	-1	5	8	6	15	25

 

시간 복잡도)

시간 복잡도는 각각의 값을 채우는데 더한게 좋은가 혼자 있는게 좋은가를 1번 비교하기 때문에 각각 O(1)의 시간 복잡도를 가진다. n개가 있을 경우 O(n)의 시간 복잡도를 가진다.

 

동적 계획법은 다른 방법에 비해 코드가 간결해지고 굉장히 빠르게 해결할 수 있음을 확인할 수 있다.