학부 CS/알고리즘

알고리즘(6) : 동적 계획 알고리즘, DP(1) - 모든 쌍 최단 경로, 연속된 행렬 곱셈

Kstone 2025. 1. 16. 12:11

동적 계획 알고리즘(Dynamic Programming)이란?

동적 계획 알고리즘은 최적화 문제를 해결하는 알고리즘에 해당한다. 문제를 크게 세 단계로 나누어 해결하는데,

1. 먼저 입력 크기가 작은 부분 문제들을 모두 해결해 그 값을 저장한다.

2. 그 해들을 이용하여 보다 큰 크기의 부분 문제를 해결한다.

3. 최종적으로 원래 주어진 입력의 문제를 해결한다.

결국 큰 문제를 작은 문제로 쪼개서, 그 답을 저장해두고 재활용(기억하면서 풀기)한다는 것이다.

얼핏보면 분할 정복 아니야? 라고 할 수 있지만, 분할 정복은 그 답을 저장해두지는 않는다.

DP는 분할 정복 + 최적부분 구조를 합친 알고리즘이다. 뭔지 모르겠다면 그리디와 분할 정복 포스트를 보고오자.

 

분할 정복을 사용하긴 하지만 크게 다른 점이 하나 있다. 바로 DP는 Bottom-up 방식으로 문제를 해결한다.

또한 분할 정복은 각 부분 문제가 서로 독립적이었지만, DP는 중복되는 부분이 존재해 종속적이다.( 쓴걸 또 쓴다 )

이전에 분할 정복 포스트에서 입력의 크기때문에 피보나치 수열 문제를 풀 수 없다고 했는데,

DP를 이용하면 그런 걱정 없이 피보나치 수열을 구해낼 수 있다. 그 값을 저장하기 때문이다.

int fibo(int n) {
	int i, f[n];
	f[0] = 0, f[1] = 1;		// 초기 값 저장
	for(i=2; i<=n; i++)
		f[i] = f[i-1] + f[i-2];		// 저장된 값을 바탕으로 다음 값을 얻음
	return f[n];
}

 

위의 코드가 DP로 푼 피보나치 수 찾기 문제이다. 매우 간단하게 풀린다! 자연스레 $O(n)$임을 알 수 있다.

 

따라서 동적 계획 알고리즘으로 문제를 풀려면, 먼저 최소 단위의 부분 문제의 해를 각각 구해 저장해야한다.

이때 최소 단위 문제를 어떻게 정의할지 정하는 것이 매우 중요하다.

만약 D, E, F ,G를 최소 단위 부분 문제로 지정하고 해를 구했다면, 이후 이 저장한 값들을 이용해 더 큰 문제를 푼다.

그림에서는 B를 해결하는데 D, E, G를 사용했고 C를 해결하는데 E, F, G를 사용했다.

위에서 얘기했듯이 한 번 사용한 부분 문제의 해를 중복해서 사용할 수 있고, 그림에서도 사용된 모습이다.

 

DP 알고리즘에는 부분 문제들 사이에 의존적 관계가 존재한다. ( D, E, G가 B를 해결하는데 사용되는 등 )

이러한 의존적 관계는 문제 유형과 입력에 따라 다르고, 대부분 이 관계가 바로 보이지 않기 때문에

이를 '함축적 순서'(implicit order)라고 한다. 후에 각 알고리즘마다 이를 알아보게 되니 잘 기억해두자.

 

또한 DP 알고리즘에는 최적성의 원리가 적용된다. 이는 문제의 최적해가 부분 문제의 최적해로 구성된다는 것으로,

그리디 알고리즘에서도 사용되는 원리이다. 그러나 그리디 알고리즘은 항상 최적해를 얻을 수는 없었던 반면,

DP는 각 부분 문제에 대한 모든 가능성을 고려해 다음 최적해를 구하기 때문에, 항상 최적의 결과를 얻는다.

 

따라서 위의 내용들을 바탕으로 DP를 적용하고 푸는 방법을 정리하자면,

1. 문제를 분석해 최적성의 원리가 성립하는지 확인한다.

2. 주어진 문제에 대해서 최적해를 제공하는 점화식을 도출(함축적 순서를 찾아라)

3. 가장 작은 부분 문제부터 점화식의 해를 구한 뒤 이를 테이블에 저장한다.

4. 테이블에 저장된 해를 이용해 점점 입력 크기가 커지는 문제들의 해를 구한다.

모든 쌍 최단 경로 문제(All Pairs Shortest Paths), 플로이드 - 워셜 알고리즘

모든 쌍 최단 경로 문제는 각 쌍의 점 사이의 최단 경로를 찾는 문제이다.

앞서 다익스트라 알고리즘은 하나의 시작점으로부터 다른 도시들과의 최단 경로를 찾는 것이었다면,

해당 문제는 모든 도시 쌍에 대해 최단 거리를 찾는 문제로 확장된 것이다.

 

그래서 이 문제를 간단하게 푸는 방법은, 모든 도시에 대해 다익스트라 알고리즘을 반복하면 된다.

기존 다익스트라 알고리즘의 시간복잡도가 $O(n^2)$이므로, (n-1)번 반복하면 $O(n^3)$이 소요된다.

하지만 DP를 이용하면 더 쉽게 계산할 수 있는데, 해당 알고리즘이 플로이드-워셜 알고리즘이다.

사실 시간복잡도는 플로이드-워셜도 $O(n^3)$으로 동일하지만, 방법이 간단해 보다 더 효율적이다.

 

플로이드-워셜 알고리즘은 두 개의 주요한 성질을 가지고 있는데,

1. 두 정점을 잇는 최단 경로는 경유지를 거치거나 거치지 않는 경로 중 하나이다.( 정점이 3개가 필요 )

2. 만약 경유지를 거친다면, 경유지로 가는 경로 역시 최단 경로여야한다.

 

위에서 이야기 했듯이 DP로 문제를 풀 경우 부분 문제를 잘 정의해야 한다.

이를 찾기 위해 그래프의 정점의 개수가 적을 때를 생각해보자.

그림과 같이 정점이 3개만 있다면, i에서 j로 가는 경로는 i-j와 i-1-j 두개 뿐이다. 이중 짧은 것을 선택하면 된다.

여기서 점의 개수를 하나 늘리면 어떻게 될까?

2번 정점이 추가되었다. 그렇다면 i에서 j로 갈 때, 경유 가능한 점이 하나 더 늘어나는 것이다.

이런 식으로 정점을 문제에서 주어진 개수까지 늘려가면서, 1~n까지 모두 고려하면서 풀어나가면 된다.

 

이를 도식화 하기위해 $D^k_{ij}$로 표기할 것이다. k는 점 1~k까지 경유하는 것이고, i와 j는 시작점과 종점이다.

따라서 해당 기호의 값은 i에서 j로 가는 최단 경로를 뱉어주게 된다.

주의할 점은 k = 0이 될 수 있다는 것이다. 다이렉트하게 연결되는 부분이 있다면 그것이 $D^0_{ij}$이 된다.

따라서 해당 값은 선분(i, j)의 가중치라고도 할 수 있다. 이게 주어지는 입력이다.

 

그렇다면 가장 작은 문제는 바로 $D^1_{ij}$이 되는 것이다! 이를 토대로 k값을 늘려가며 찾아내면 된다.

이를 이용해 $D^1_{ij}$을 구해보자.

$D^1_{ij}$은 점 1을 경유해서 가는 경로를 고려해야 하므로, $D^1_{ij} = min\{ D^0_{i1}  + D^0_{1j} , D^0_{ij} \}$이 된다!

계속해서 $D^2_{ij}$를 구해보자. 이 경우도 간단하게 표현하면 우측과 같으므로, $D^2_{ij} = min\{ D^1_{i2}  + D^1_{2j} , D^1_{ij} \}$이 된다!

2번 정점을 경유하는 방법도 1번 정점을 경유하거나 안하는 이전 값인 $D^1$값을 사용하므로, DP로 풀어야 하는 것이다.

이렇게 반복하면 최종적으로 점 k를 고려할 때 최단 경로가 정해지게 된다.

$D^k_{ij} = min\{ D^{k-1}_{ik}  + D^{k-1}_{kj} , D^{k-1}_{ij} \}$ 의 식이 도출된다.

 

모든 쌍 최단 경로 알고리즘의 함축적 순서와 시간복잡도

함축적 순서

이로부터 알 수 있는 모든 쌍 최단 경로 문제의 함축적 순서는,

새로운 D[i, j]를 계산하기 위해 D[i, k]와 D[k, j]가 필요하다는 것이다.

입력 : 2차원 배열 D, 단, D[i, j]의 값은 선분(i, j)의 가중치이고, 존재치 않으면 값은 ∞.
       더불어 D[i, i]의 값은 항상 0.
출력 : 모든 쌍 최단 경로의 거리를 저장한 2차원 배열 D

1. for k = 1 to n
2.	for i = 1 to n(단, i != k)
3.		for j = i to n(단, j != k and j != i)
4.			D[i, j] = min{D[i, k] + D[k, j], D[i, j]}

 

따라서 설명은 어려웠지만 수도코드 자체는 매우 간단하게 나온다. 앞으로 DP문제들은 다 이런 식으로 코드는 간단하다.

함축적 순서는 수도 코드의 4번 라인에 표현되어있다. 특히 k를 가장 외부의 for문에 두는 것을 잘 기억하자.

위의 설명에서도 $D^1$ 값들을 모두 구하고, $D^2$을 구한 것을 반영하기 위해 k가 가장 바깥 for문에 있다.

시간복잡도는 딱 봐도 for문이 세개 중첩되어 있으므로 $O(n^3)$이 소요되는 것을 알 수 있다.

 

예시로 한 두개의 계산만 보여주고, 다음 알고리즘을 소개하도록 하겠다.

도시 간의 거리가 해당 그래프로 주어지고, $D^0$(직접 연결된 경로)의 값이 우측의 표와 같다고 하자.

이때 k = 1, 즉 점 1을 경유해서 가는 $D^1$을 계산한다고 가정하자.

그렇다면 수도 코드에서 i와 j는 k가 될 수 없으므로, (2, 3, 4, 5)에서 반복되게 되는데,

이때 D[2, 3]와 같은 값은 $min\{D[2,3], D[2,1] + D[1,3]\} = min\{1, ∞+2\} = 1$로 갱신이 이루어지지 않지만,

D[4, 2]는 $min\{D[4,2], D[4,1] + D[1,2]\} = min\{ ∞ , 2\} = 2$로 갱신이 이루어진다!

이런 식으로 k가 5에 도달할 때 까지 계속해서 갱신이 이루어지면 결국 모든 쌍의 최단 경로를 표로 얻게 된다.

 

플로이드-워셜 알고리즘을 사용할 때 주의할 점은, 음수 사이클이 존재하면 안된다는 것이다.

음수 사이클은 한 사이클의 가중치의 합이 음수가 되는 경우로, 이런 경우는 해당 경로를 반복해서 돌면

최단 경로가 음수가 되어 길이가 음수가 되는 모순이 생기기 때문이다.

음수 가중치는 있을 수 있지만, 음수 사이클은 존재해서는 안됨을 기억하자.

연속된 행렬 곱셈

연속된 행렬 곱셈 문제는 행렬 곱셈의 효율성을 높이기 위해 고안된 알고리즘이다.

행렬을 세 개 이상 연속해서 곱하는 경우 결합법칙이 성립하는데, 이때 어떤 순서로 곱하냐에 따라 곱셈 횟수가 달라진다.

따라서 해당 문제는 가장 스칼라 곱셈 횟수가 적은 최적의 곱셈 순서를 찾아주는 문제이다.

 

먼저 행렬 곱셈의 성질에 대해 알아야 하는데, C = AB(A, B, C는 모두 행렬)인 행렬곱이 있다고 하자.

해당 행렬곱이 성립하려면 A의 열의 개수와 B의 행의 개수가 같아야 한다.

A가 (p x q)행렬, B가 (q x r)행렬이라면 C는 (p x r)행렬이 된다. 이때의 스칼라 곱 횟수는 p x q x r번이다.

왜 그런지는 밑의 행렬 곱셈 코드을 보면 이해가 된다.

void matrix_mul(int A[][MAX], int B[][MAX], int C[][MAX], int p, int q, int r) {
    int i, j, k;
    for(i=0; i<p; i++) {
    	for(j=0; j<r; j++) {
        	C[i][j] = 0;
            for(k=0; k<q; k++) {
            	C[i][j] = C[i][j] + A[i][k] * B[k][j];
            }
        }
    }
}

 

선형대수학을 이수했다면 아는 내용이겠지만, 혹시나 해서 넣었다.

 

만약 행렬 네 개가 각각 $A_{10*5}, B_{5*20}, C_{20*4}, D_{4*30}$일 때, ABCD의 스칼라 곱셈 횟수를 순서에 따라 나누면

다음과 같다. 순서에 따라 곱셈 횟수가 천차만별이고, 이는 곧 연산 속도와 시간에 영향을 주게 된다.

따라서 DP를 통해 이 곱셈 횟수가 최소가 되는 순서를 찾는 알고리즘을 구현할 것이다.

 

여기서도 브루트 포스를 이용해서 생각해볼 수 있는데, 모든 가능한 경우에 대해 스칼라 곱셈 횟수를 구해 비교하면,

$X_n$을 n개의 행렬을 곱하는 가능한 모든 곱셈 순서의 수라고 했을 때, 다음 세 가지 경우의 수를 합한 것과 같다.

1. $M_1$을 가장 나중에 곱하는 경우 = $M_1(M_2M_3M_4...M_n)$의 순서로 곱함 = $X_{n-1}$

2. $M_n$을 가장 나중에 곱하는 경우 = $(M_1M_2M_3...M_{n-1})M_n$의 순서로 곱함 = $X_{n-1}$

3. 나머지 모든 경우의 수 = α( 두개 먼저 곱하고 나머지 곱하기 같은 경우 )

따라서, $X_n=2X_{n-1}+ \alpha  = 2X_{n-1}>=2^2X_{n-2}>=2^3X_{n-3}>=2^{n-2}X_2=2^{n-2}$가 된다.

결국 지수 시간이 걸리므로 이 또한 현실적으로 풀기 불가능한 수준이다.

 

우선 연속된 행렬 곱셈 문제를 DP를 통해 풀 수 있는지 확인해보자.

당연하게도, 연산 법칙에 따라 행렬곱 $M_1M_2M_3M_4$에서 최적 순서가 $M_1((M_2M_3)M_4)$ 이라면,

세 개의 행렬 곱셈 $M_2M_3M_4$의 최적 순서는 당연히 $(M_2M_3)M_4$가 된다. 따라서 최적 부분 구조를 갖는다.

 

이제 문제를 풀기 위해 문제를 순환적으로 정의해야한다. 최우선 목표는 최소 스칼라 곱셈 횟수를 구하는 것으로,

$c_i$를 행렬 $M_i$의 열의 수라 하면 $M_i$와 인접한 $M_{i+1}$의 행의 수가 $c_i$가 된다.( $M_1$의 행 수는 $c_0$ )

따라서 $M_i$는 $c_{i-1}*c_i$ 행렬이고, 행렬 곱셈 $M_iM_{i+1}...M_{j-1}M_j$의 결과는 항상 $c_{i-1}*c_j$ 행렬이 된다.

이를 이용해서 최종적으로는 n개의 연속된 행렬이 주어졌을 때 최적 곱셈 순서를 알아내야 한다.

이때 행렬곱은 교환법칙이 성립하지 않으므로, 인접한 행렬끼리만 곱할 수 있다. 따라서 경우의 수가 (n-1)가지만 나온다.

n-1가지 경우

 

이 중 하나의 경우가 최적 순서가 되며, 만약 하나를 찾으면 그 내부도 최적의 순서로 곱해야한다.

그래서 이 정보들을 일반화하면 1과 n을 각각 i와 j로 바꾸어 생각하면 된다. 총 j-i가지 경우에 대해 고려하면 된다.

 

만약 $M_iM_{i+1}...M_{j-1}M_j$의 최소 스칼라 곱셈 횟수를 S(i, j)라고 한다면, j-i개의 분할에 대해서 각각

다음과 같은 스칼라 곱셈 횟수가 계산된다. 따라서 해당 값들 중 가장 작은 값을 사용하면 되는 것이다.

위의 식을 잘 기억하자. 해당 식이 함축적 순서가 된다. 만약 i = j라면 행렬이 한 개이므로, 곱셈 횟수는 0이 된다.

작은 부분 문제부터 해결해야 하므로, 가장 작은 부분 문제는 두 행렬의 곱이다. 순서 필요 없이 그냥 곱하면 된다.

그럼 그 다음 문제는 세 개의 행렬의 곱, 네 개의 행렬,,,, 최종적으로 n개의 행렬 곱의 곱셈 횟수를 구해나가면 된다.

이를 표로 만들어서 보면 이런 모양인데,

S[][] 1 2 3 4 5 6 ... n-1 n
1 0               S[1][n]
2   0              
3     0 S[3][6]      
4       0        
5         0      
6           0      
...             0    
n-1               0  
n                 0

 

편의상 S[i][i]가 모여있는 대각선을 0번 대각선이라고 하겠다. 0번 대각선은 하나의 행렬이므로 값이 모두 0이고,

대각선 위치를 옮길 수록 곱하는 행렬 개수가 변하므로, 1번 대각선, 2번 대각선,,, 순차대로 계산해 S[1][n]을 구한다.

예로 S[3][6]을 구하는 경우, 1번끼리 더하는 경우와 2번끼리 더하는 경우 두 가지가 있는데, 이 중 작은 값이 S[3][6]이 된다.

 

그러나 이런 식으로 정답을 구하면, 최적의 경우의 곱셈 횟수만 알 수 있다. 곱셈 순서까지 알아내려면 어떻게 해야할까?

위의 함축적 순서의 식을 보면, 최소 곱셈 횟수가 정해질 때 k의 값도 같이 정해지는 것을 알 수 있다.

k 값이 의미하는 것은 최적의 순서가 S[i][k] + S[k][j] 라는 것으로, k번째 행렬까지 곱하고 그 뒤로는 끊는다는 것이다.

그럼 k 값을 저장한 배열을 하나 만들어둔다면 자연스레 순서까지 알아낼 수 있다!

따라서 횟수를 저장하는 S배열 외에 T라는 배열을 추가해 T[i][j] = k와 같은 식으로 값을 저장해 순서를 파악하면 된다.

 

입력 : 행렬의 수와 각 행렬의 행과 열 개수
출력 : 최적의 곱셈 순서의 곱셈 횟수

1.	int matrix_DP(int C[], int n) {
2.	 int S[MAX][MAX], T[MAX][MAX];
3.	 int d, i, j, k;
4.	 for(i=1; i<=n; i++) S[i][i] = T[i][i] = 0;		// 0번 대각선 초기화
5.	 for(d=1; d<=n-1; d++) {		// 대각선 수-1번 반복
6.	 	for(i=1; i<=n-d; i++) {		// 대각선 1부터 대각선 n-1까지 채워나간다
7.	 	 j = i + d;					// d = j - i 식을 이용
8.	 	 S[i][j] = ∞;
9.	 	 for(k=i; k<=j-1; k++) {	// 최적의 곱셈 횟수 구하는 과정
10.	 	  if(S[i][k] + S[k+1][j] + C[i-1]*C[k]*C[j] < S[i][j]) {
11.	 	 	 S[i][j] = S[i][k] + S[k+1][j] + C[i-1]*C[k]*C[j];
12.	 	 	 T[i][j] = k;
13.	 	  }
14.		 }
15.	 	}
16.	  }
17.	return S[1][n]
18.	}

 

최적의 곱셈순서의 횟수를 리턴해주는 함수는 다음과 같고, 순서를 출력하는 함수는 다음과 같다.

 

void optimal_order(int T[][MAX], int i, int j) {
	if(i == j) printf("M%d", i);
    else {
    	printf("(");
        optimal_order(T, i, T[i][j]);
        optimal_order(T, T[i][j]+1, j);
        printf(")");
    }
}

 

연속된 행렬 곱셈 알고리즘의 시간복잡도

 

수도코드를 보면 시간복잡도를 결정하는 주 요인은 5, 6, 9번 라인임을 알 수 있다. 식을 풀어보면

 

$T(n) = \sum_{d=1}^{n-1}\sum_{i=1}^{n-d}(j-i)$


$=  \sum_{d=1}^{n-1}\sum_{i=1}^{n-d}d$


$=  \sum_{d=1}^{n-1}(n-d)*d$


$=  \sum_{d=1}^{n-1}(nd-d^2)$


$=  n\sum_{d=1}^{n-1}d - \sum_{d=1}^{n-1}d^2 = \frac{n^2(n-1)}{2} -  \frac{(n-1)n(2n-1)}{6} = \Theta (n^3)$

 

으로, 결국 시간복잡도는 $O(n^3)$임을 알 수 있다.

 

DP의 첫 번째 포스트는 여기서 마무리하고, 두 번째 포스트에서 나머지 문제들을 다루도록 하겠다.

DP 또한 두 장의 포스트로 구성될 예정이다!