[Algorithms] Dynamic Programming

 

 

/*
	강의 정리
*/

Dynamic Programming(동적계획법) 이란?

처음에 주어진 큰 문제를 여러개의 작은 문제로 나누어 푸는 방법을 말합니다. 어랏? Divide&Conquer(분할정복기법)랑 같은거 아닌가? 할 수도 있지만, 큰 차이점 하나가 있습니다. Dynamic Programming 은 중복 계산을 하지 않는다는 점입니다. Divide&Conquer 에서는 큰 문제를 여러개의 작은 문제로 나눈 후에, 작은 문제를 계산하고 그 결과를 결합해 윗 단계의 문제를 해결하는 방식이였습니다. Dynamic Programming 에서는 이와 거의 유사하지만, 나눠진 작은 문제들 중 이미 앞에 계산한 적이 있는 연산이라면 이를 중복해서 계산하지 않고 이전의 결과값을 불러와 사용합니다. 이러한 이전 연산 결과를 저장한다는 특징 때문에, Divide&Conquer 보다 추가적인 Space 가 필요한 경우가 발생합니다.

Dynamic Programming 을 적용하기 위한 조건

모든 문제에 이런 Dynamic Programming 을 적용할 수 있으면 좋겠지만.. 적용하기 위한 조건이 있습니다.
1. Overlapping Subproblems : 임의의 Subproblem을 여러번 만난다 -> 여러번 만나야 연산 결과 저장한 보람이 있으니깐요!
2. Optimal Substructure : 현재 만난 subproblem 은 그 문제의 substructure 을 이용해 해결한다. 이때 그 문제의 subproblem 또한 Optimal 해야 한다.

Dynamic Programming 의 접근 방법

Dyanmic Programming 은 크게 두가지의 접근 방법이 있습니다.
1. top-down approach(하향식 접근) : 큰 문제부터 출발해서 더이상 쪼갤 수 없을 때까지 쪼개고 해결. 보통 재귀(Recursion) 으로 구현
2. bottom-up approach(상향식 접근) : 처음부터 작은 문제로 시작하고, 문제의 크기를 점점 늘려가며 해결. 보통 반복문(Loop) 으로 구현

본 포스팅에서는 하향식 접근 방식의 Dynamic Programming 만 다룰 것입니다. 

Dynamic Programming Version of a Recursive Algorithm(Top-Down Approach)

Dynamic Programming 은 앞서 서술했듯이 중복 연산을 없애고 연산 결과를 저장하는 방식을 채택함으로써, 공간과 속도를 거래한 셈이 됩니다. Subproblems 들의 솔루션(연산 결과)들은 soln 이라는 이름의 배열에 저장됩니다. Subproblem Q를 해결해야 할 때, 재귀를 호출하기 전 먼저 soln 에 저장된 솔루션이 있는지 먼저 체크합니다. 만약 값이 이미 있다면 이를 사용하고 재귀를 호출하지 않으며, 없다면 재귀를 호출하여 연산 결과를 soln 에 저장합니다.

Dynamic Programming 의 예시로 피보나치 수를 구하는 Pseudo-Code 를 보겠습니다. Dynamic Programming 의 두가지 접근 방식을 이해하기 위해서 Bottom-Up Approach 방식의 Pseudo-Code 도 작성해놓았습니다.

// Top-Down Approach
fipDPwrap_td(n) // n : 구하려는 피보나치 n번째 항
	Dict soln = create(n); // size가 n+1 인 Array 생성
	return fibDP_td(soln, n); // Entry Point

fibDP_td(soln, k)
	int fib, f1, f2;
	if (k < 2) 
		fib = k;
	else
		if (member(soln, k-1) == false) // 피보나치 k-1 번째 항이 저장되어 있지 않나요..?
			f1 = fibDP_td(soln, k-1); // 그러면 재귀 함수 호출로 계산!
		else // 헐 k-1 번째 항이 저장되어 있나요?
			f1 = retrieve(soln, k-1); // 그러면 가져와!
		if (member(soln, k-2) == false) // 피보나치 k-2 번째 항이 저장되어 있지 않나요..?
			f2 = fibDP_td(soln, k-2); // 그러면 재귀 함수 호출로 계산!
		else // 헐 k-2 번째 항이 저장되어 있나요?
			f2 = retrieve(soln, k-2); // 그러면 가져와!
        
		fib = f1 + f2; // 위에서 계산 또는 가져온 k-1 번째, k-2 번째 피보나치 수를 더해서 k 번째 피보나치 수를 구하기
	store(soln, k, fib); // 이번에 계산한 k 번째 피보나치 수를 soln 에 저장. 나중에 또 써먹어야지
	return fib; // 계산한 값 반환

// Bottom-Up Approach

fipDPwrap_bu(n) // n : 구하려는 피보나치 n번째 항
	Dict soln = create(n); // size가 n+1 인 Array 생성
	return fibDP_bu(soln, n); // Entry Point

fibDP_bu(soln, k)
	int fib, f1, f2;
	if (k < 2) 
		fib = k;
	else
		if (member(soln, k-1) == false) // 피보나치 k-1 번째 항이 저장되어 있지 않나요..?
			f1 = fibDP_bu(soln, k-1); // 그러면 재귀 함수 호출로 계산!
		else // 헐 k-1 번째 항이 저장되어 있나요?
			f1 = retrieve(soln, k-1); // 그러면 가져와!
		if (member(soln, k-2) == false) // 피보나치 k-2 번째 항이 저장되어 있지 않나요..?
			f2 = fibDP_bu(soln, k-2); // 그러면 재귀 함수 호출로 계산!
		else // 헐 k-2 번째 항이 저장되어 있나요?
			f2 = retrieve(soln, k-2); // 그러면 가져와!

 

Matrix-Chain Multiplication

Dynamic Programming 을 활용할 수 있는 문제가 위의 피보나치 수열을 구하는 문제 말고도 또 있습니다. 바로 체인처럼 이어진 행렬을 곱하는 연산에서, 최소 연산으로 해결할 수 있는 순서를 찾는 문제입니다. 이를 Matrix-Chain Multiplication 이라고 합니다.

체인처럼 이어진 n 개의 행렬 $<A_{1}, A_{2}, ..., A_{n}>$ 이 주어졌을 때, 우리는 $A_{1} * A_{2} * A_{3} * ... A_{n}$ 의 결과를 연산해야 합니다. 결과를 구할 때 필요한 연산량은 아래의 그림처럼 구할 수 있습니다.

만약 $A_{1}$ = 30 x 1, $A_{2}$ = 1 x 40, $A_{3}$ = 40 x 10, $A_{4}$ = 10 x 25 와 같이 행렬이 들어왔다면 아래와 같은 경우의 수가 나옵니다.

1. $((A_{1}*A_{2})*A_{3})*A_{4}$ : 30 x 1 x 40 + 30 x 40 x 10 + 30 x 10 x 25 = 20,700 번의 연산이 필요
2. $A_{1}*(A_{2}*(A_{3}*A_{4}))$ : 40 x 10 x 25 + 1 x 40 x 25 + 30 x 1 x 25 = 11,750 번의 연산이 필요
3. $(A_{1}*A_{2})*(A_{3}*A_{4})$ : 30 x 1 x 40 + 40 x 10 x 25 + 30 x 40 x 25 = 41,200 번의 연산이 필요
4. $A_{1}*((A_{2}*A_{3})*A_{4})$ : 1 x 40 x 10 + 1 x 10 x 25 + 30 x 1 x 25 = 1,400 번의 연산이 필요

위와 같이 괄호를 어디에 씌우냐에 따라서 필요한 연산량이 달라집니다. 위 경우의 수 중 4번째와 같이 최소 연산으로 행렬의 곱셈을 할 수 있는, Optimal Parenthesization 을 찾아야 합니다.

Step 1. The structure of an Optimal Parenthesization

Ai 부터 Aj 까지의 행렬을 index k 기준으로 두개의 부분으로 나누어줍니다. 그럼 $A_{i}$~$A_{k}$ 와 $A_{k+1}$~$A_{j}$ 와 같이 나뉘게 됩니다. 이때 k 는 i ≤ k < j 의 관계입니다. 그럼 Cost(곱셈 연산 수)를 아래와 같이 계산할 수 있게 됩니다.

$  Cost\,=\,(cost\,of\,computing\,A_{i..k})\,+\,(cost\,of\,computing\,A_{k+1..j})\,+\,(cost\,of\,multiplying\,them)$

$ A_{i}$~$A_{k} $까지 곱셈 연산 후 나온 결과 행렬을 X, $ A_{k+1}$~$A_{j}$ 까지 곱셈 연산 후 나온 결과 행렬을 Y 라고 했을 때, 최종 결과 행렬을 구하기 위해서 X 와 Y 를 곱셈 연산해야 합니다. 이때 드는 비용이 마지막에 더해주는 항입니다.

이때, $ A_{i}$~$A_{k}$ 와 $ A_{k+1}$~$A_{j} $ 는 어떠한 k 값에 대해서 optimal 해야 합니다. 최소 비용이 발생하는 k 값을 찾기 위해서는, 모든 경우의 수를 계산해보아야 합니다.

Step 2. A Recursive Solution

우리는 이 문제를 해결하기 위해서 2 개의 Dynamic Table 이 필요합니다. m table 과 s 테이블입니다.

m table
Ai..Aj 를 계산할 때 필요한 Scalar Multiplications 의 최솟값을 저장하는 테이블입니다. 만약 i와 j가 둘다 0 일 때, m[i, j] 는 0입니다. A0 ~ A0 까지 곱하는 연산은 수행되지 않기 때문입니다. 
$ m[i,j] = min\,{m[i,\,k]\,+\,m[k+1,\,j]\,+\,p_{i-1}p_{k}p_{j}}\,\,(if\,\,i<j) $
$ m[i,\,k]\,=\,p_{i-1}\,*\,p_{k} $
$ m[k+1,\,j]\,=\,p_{k}\,*\,p_{j} $
$ p_{i-1}p_{k}p_{j} $ : i~k 와 k+1~j  의 결과로 나온 2개의 행렬을 곱하는 데에 필요한 연산 수

s table
m table 특정한 k 를 기준으로 나누어서 연산했을 때, 필요한 연산 수를 저장하는 table 이라고 한다면, s table 은 그 k 의 위치를 저장하는 table 입니다. 사실 s table 은 밑에서 할 step 4 에서 필요합니다. 즉, step 4를 수행하지 않을 것이라면 s table 은 필요하지 않습니다. 

입력값으로 들어오는 행렬의 수를 n 개라고 할 때, 두 개의 table 모두 n x n 형태의 2차원 배열입니다. 

Step 3. Computing the Optimal Costs

이제 본격적으로, Optimal Costs 를 구해보겠습니다. 먼저 Pseudo-Code 입니다.

MATRIX-CHAIN-ORDER(p)
	n <- length[p] - 1 // 행렬의 차원 입력값인 p 는, 행렬의 개수 + 1 개입니다.
	for i <- to n
		m[i, i] <- 0 // m table 의 대각선을 0으로 초기화
	for l <- 2 to n // l : 2~n // Chain Length
		for i <- 1 to n - l + 1
			j <- i + l - 1
			m[i, j] <- ∞
			for k <- i to j - 1
				q <- m[i, k] + m[k+1, j] + p[i-1] * p[k] * p[j]
				if q < m[i, j]
					m[i, j] <- q // Optimal Costs 업데이트
					s[i, j] <- k // Optimal Costs 가 발생한 k 값 저장/업데이트
	return m and s

$ A_{1} = 30\ast1, A_{2}=1\ast40, A_{3}=40\ast10, A_{4}=10\ast25$
예시로 사용할 행렬이 위와 같을 때, 위 코드의 수행 방식을 그림으로 알아보겠습니다. 

m table 에서 j<i 인 영역을 사용하지 않는 이유는, j<i 라면 $A_{i} ~ A_{j}$의 행렬 곱이 정의되지 않기 때문입니다. 가장 앞 행렬이 i 번째, 가장 마지막 행렬이 j 번째여야 하므로, j가 i 보다 작을 수 없습니다.
비슷한 이유로 s table에서 j <= i 인 영역을 사용하지 않습니다. j=i 일 때도 사용하지 않는 이유는, s table 은 $A_{i} ~ A_{j} $사이에 나누는 지점 k 값을 저장하는 형태인데 i와 j 가 같다면 나누는 지점 k 도 정의되지 않기 때문입니다.

위에서 계산한 방식으로, 우리는 Optimal Costs 를 구할 수 있습니다.

 

Step 4. Constructing an Optimal Solution

앞에서 구한 최소 비용이 드는 순서(과정)을 만드는 단계입니다. 우리는 앞서 1,400 번의 곱셈 연산이 최소 비용이라는 것을 알아냈습니다. 이 단계에서는 이 곱셈 연산이 발생하는 Optimal Parenthesization(Solution) 을 만드는 단계로, 이 단계에서 찾아내는 결과는 A1*((A2*A3)*A4) 입니다. 아래는 이 결과를 출력하는 Pseudo-Code 입니다.

PRINT_OPTIMAL_PARENS(s, i, j)
	if i = j // Base Case
		then print "A"i // Ai 를 출력. 
	else
		print "(" // 여는 괄호 출력
		PRINT_OPTIMAL_PARENS(s, i, s[i, j]) // s[i, j] 는 k 값을 의미. i~k
		PRINT_OPTIMAL_PARENS(s, s[i, j] + 1, j) // k+1 ~ j
		print ")" // 닫는 괄호 출력

위 알고리즘의 수행 방식은 아래의 그림처럼 트리로 표현할 수 있습니다.

 

수행 시간을 분석해보면, 하나의 노드는 상수 시간(O(1))에 처리 가능합니다. Proper Binary Tree 라고 가정할 때, Leaf Node 가 n 개라고 할 때, Internal Node 는 n-1 개입니다. 이때의 총 수행 시간은 O(2n+1) time == O(n) time 입니다. 즉 Linear time 에 수행 가능합니다. 공간 복잡도를 보면, 위 코드가 수행되기 위해서는 s table 이 필요합니다. 즉 O(n^2) space 가 필요합니다.

 

 

Dynamic Programming 를 활용해볼 수 있는 문제입니다. Top-Down Approach, Bottom-Up Approach 두가지 방식으로 모두 풀어보시는걸 추천드립니다.
- LeetCode
- Baekjoon

Fibonacci Number - LeetCode

2747번: 피보나치 수

 

제가 LeetCode 문제를 해결한 코드는 아래와 같습니다.

// Top-Down Approach
class Solution
{
private:
    int F[33];

public:
    int fibon(int n)
    {
        int ans, f1, f2;
        if (n < 2)
            return n;
        else
        {
            if (F[n - 1] == -1)
                f1 = fibon(n - 1);
            else
                f1 = F[n - 1];

            if (F[n - 2] == -1)
                f2 = fibon(n - 2);
            else
                f2 = F[n - 2];

            ans = f1 + f2;
            F[n] = ans;
            return ans;
        }
    }

    int fib(int n)
    {
        memset(F, -1, 33 * sizeof(int));
        int ans = fibon(n);
        return ans;
    }
};

// Bottom-Up Approach

class Solution {
public:
    int fib(int n) {
        if (n==0) return 0;
        int *F = new int[n+1]; // Array
        F[0] = 0; F[1] = 1; // Initialization
        for (int i=2; i<=n; i++) 
            F[i] = F[i-1] + F[i-2];
        return F[n];
    }
};

 

Top-Down Approach 수행시간/공간복잡도

Bottom-Up Approach 수행시간/공간복잡도