[알고리즘] 동적 계획법(Dynamic Programming)

동적 계획법 푸는 방법 (DP 풀이)

알고리즘 중 하나인 동적 계획법, 사실 알고리즘 자체보다는 순발력을 요하는 경우가 잦아 많은 연습이 필요한 알고리즘이다. 이러한 동적 계획법에 대해 소개하고 어떻게 풀이해야 하는지에 대한 글이 있어 소개하고자 한다. 결론은 많은 연습과 직관이지만, 풀이 단계를 체계적으로 나누고 실제로 적용해봄에 의의가 있다고 생각된다.

(원문: www.geeksforgeeks.org/solve-dynamic-programming-problem/)

 

 

동적 계획법(DP, Dynamic Programming)은 다항식 시간의 특정 유형의 문제를 해결하는 기술이다. 동적 계획법은 지수 시간의 브루트 포스 방식보다 빠르며 정확하다. 동적 계획법을 풀기 위해선 선행 학습되어야 할 내용들이 있다.

• 중복된 하위 문제
• 최적 부분 구조

DP 풀이 단계

1) 해결하고자 하는 문제가 DP 문제인지 확인한다.
2) 최소한의 매개변수를 가지고 상태 표현식(state expression)을 결정한다.
3) 상태의 관계를 수립한다. -> 점화식 세우기
4) Tabulation(테이블-상향식) or Memoization(메모-하향식)을 이용하여 문제를 해결한다.

 

1단계: 어떻게 문제를 DP 문제로 분류할 수 있는가?

• 일반적으로, 특정 양을 최대화 또는 최소화해야 하는 모든 문제 또는 특정 조건 또는 특정 확률 문제에서 배열을 계산해야 하는 문제를 동적 계획법을 사용하여 해결할 수 있다.
• 모든 동적 계획법 문제는 중복된 하위 문제 속성을 만족하며, 대부분의 고전적인 DP 문제 또한 최적 부분 구조를 만족시킨다. 일단 주어진 문제에서 이러한 특징들이 확인되면, DP를 적용하여 해결할 수 있다.

 

2단계: 상태 결정하기

• DP 문제는 모두 상태와 전환에 관한 것들이다. 두 번째 단계는 상태 전환이 선택한 상태 정의에 따라 달라지기 때문에 매우 신중하게 수행되어야 하는 가장 기본적인 단계이다. 이제 "상태"라는 용어가 무엇을 의미하는지 살펴보도록 하자.
• 상태: 상태는 특정 위치를 고유하게 식별하거나 주어진 문제에 서있는 매개 변수 집합으로 정의할 수 있다. 이 매개 변수 셋은 메모리를 줄이기 위해 가능한 한 작아야 한다.
• 예 : 유명한 배낭 문제(BOJ)에서 두 개의 매개 변수 index와 weight, 즉 DP[index][weight]로 상태를 정의할 수 있다. 여기서 DP[index][weight]는 범위 0부터 자루의 용량이 있는 인덱스까지 항목을 가중치로 정해서 얻을 수 있는 최대 수익을 알려준다. 결국 여기서 매개 변수 인덱스와 가중치를 함께 사용하면 배낭 문제의 하위 문제를 고유하게 식별할 수 있다.
• 따라서 첫 번째 단계는 문제가 DP 문제임을 확인한 후 문제의 상태를 결정하는 것이다. 알고 있듯이 DP는 계산된 결과를 사용하여 최종 결과를 공식화하는 문제다. 따라서 다음 단계에서 현재 상태와 이전 상태 간의 관계를 찾아야 한다.

 

3 단계 : 상태 간의 관계 형성 (점화식 세우기)

이 부분은 DP 문제를 해결하는 데 가장 어려운 부분이며 많은 직감, 관찰 및 연습이 필요하다. 예시를 통해 살펴보자.

유사한 문제(BOJ)

3 개의 숫자 {1, 3, 5}가 주어지고, 주어진 세 숫자의 합을 사용하여 숫자 'N'을 형성할 수 있는 총 방법 수를 구하라 (반복 및 다른 배열 허용).

6을 형성하는 총 방법 수 : 8
1 + 1 + 1 + 1 + 1 + 1
1 + 1 + 1 + 3
1 + 1 + 3 + 1
1 + 3 + 1 + 1
3 + 1 + 1 + 1
3 + 3
1 + 5
5 + 1

이 문제에 대해 동적으로 생각해보자. 우선, 주어진 문제에 대한 상태를 결정해야 한다. 모든 하위 문제를 고유하게 식별할 수 있는 매개 변수 n을 사용하여 상태를 결정한다. 따라서 상태 dp는 state(n)처럼 보일 것이다. 여기서 state(n)은 {1, 3, 5}를 요소로 사용하여 n을 형성하는 총 배열 수를 의미한다. 이제 state(n)을 계산해야 한다.

 

그래서 여기에 직관이 필요하다. 주어진 숫자를 형성하기 위해 1, 3 또는 5 만 사용할 수 있다. n = 1,2,3,4,5,6에 대한 결과를 안다고 가정해보자. 우리는 상태 (n = 1), 상태 (n = 2), 상태 (n = 3) ……… 상태 (n = 6) 이제 상태 (n = 7)의 결과를 알고 싶다. 1, 3, 5 만 더할 수 있다. 이제 다음 3 가지 방법으로 총 7을 얻을 수 있다.

 

1) 가능한 모든 상태 조합에 1 더하기 (n = 6)

예 : [(1 + 1 + 1 + 1 + 1 + 1) + 1]

[(1 + 1 + 1 + 3) + 1]

[(1 + 1 + 3 + 1) + 1]

[(1 + 3 + 1 + 1) + 1]

[(3 + 1 + 1 + 1) + 1]

[(3 + 3) + 1]

[(1 + 5) + 1]

[(5 + 1) + 1]

 

2) 가능한 모든 상태 조합에 3을 더하기 (n = 4)

예 : [(1 + 1 + 1 + 1) + 3]

[(1 + 3) + 3]

[(3 + 1) + 3]

 

3) 가능한 모든 상태 조합에 5 더하기 (n = 2)

예 : [(1 + 1) + 5]

 

이제 신중하게 위의 세 가지 경우가 합계 7을 형성할 수 있는 모든 가능한 방법을 포함하고 있다고 스스로 검증해봐야 한다. 검증 결과에 따라 state (7) = 상태 (6) + 상태 (4) + 상태 (2) 또는 state (7) = 상태 (7-1) + 상태 (7-3) + 상태 (7-5)가 된다. 일반화시키면 상태 (n) = 상태 (n-1) + 상태 (n-3) + 상태 (n-5)가 된다. 코드는 다음과 같다.

 

C++

// Returns the number of arrangements to 
// form 'n' 
int solve(int n)
{ 
// base case
if (n < 1) 
	return 0;
if (n == 1) 
	return 1; 

return solve(n-1) + solve(n-3) + solve(n-5);
} 

Python

# Returns the number of arrangements to 
# form 'n' 
def solve(n):

# Base case
if n < 1:
	return 0
if n == 1:
	return 1

return (solve(n - 1) +
		solve(n - 3) +
		solve(n - 5))

# This code is contributed by GauriShankarBadola

위의 코드는 동일한 상태를 재귀적으로 반복해서 계산하므로 연산 시간이 기하급수적으로 늘어난다. 따라서 memoization을 추가한다.

 

4 단계 : 상태에 대한 memoization(메모) 또는 tabulation(테이블) 추가

이것은 동적 계획법 풀이의 가장 쉬운 부분이다. 계산된 상태를 저장해두면 다음에 해당 상태가 필요할 때 메모리에서 직접 사용할 수 있다.

 

위 코드에 memoization을 추가한 코드

C++

// initialize to -1
int dp[MAXN];

// this function returns the number of 
// arrangements to form 'n' 
int solve(int n)
{ 
// base case
if (n < 1) 
	return 0;
if (n == 0)
	return 1;
if (n == 1) 
	return 1;

// checking if already calculated
if (dp[n]!=-1) 
	return dp[n];

// storing the result and returning
return dp[n] = solve(n-1) + solve(n-3) + solve(n-5);
}

Python

# This function returns the number of
# arrangements to form 'n'

# lookup dictionary/hashmap is initialized
def solve(n, lookup = {}):
	
	# Base cases
	# negative number can't be 
	# produced, return 0
	if n < 1:
		return 0

	# 0 can be produced by not 
	# taking any number whereas 
	# 1 can be produced by just taking 1
	if n == 0 or n == 1:
		return 1

	# Checking if number of way for
	# producing n is already calculated 
	# or not if calculated, return that,
	# otherwise calulcate and then return
	if n not in lookup:
		lookup[n] = (solve(n - 1) +
					solve(n - 3) +
					solve(n - 5))
					
	return lookup[n]

# This code is contributed by GauriShankarBadola

또 다른 방법은 표를 추가하고 풀이를 반복적으로 만드는 것(Bottom-Up)이다. 자세한 내용은 tabulation and memoization를 참조하자.

동적 프로그래밍에는 많은 연습이 필요하다. 여기에서 다양한 DP문제들을 살펴볼 수 있다.