[알고리즘] 동적계획 - 이항계수, 플로이드-와샬, 연쇄행렬곱셈

동적계획 알고리즘이란?

 

동적계획은 분할한 입력사례를 재귀 호출해 답을 얻고, 그 보다 작은 입력사례의 답을 먼저 구해 저장해놓고, 필요하면 꺼내 쓰는 알고리즘이다.

 

분할정복과는 달리 상향식(bottom-up) 접근 방법이다. 

 

동적계획 알고리즘의 개발단계는 다음과 같다.

 

1. 문제의 입력사례에 대해서 해답을 계산하는 재귀 관계식을 세운다.

 

2. 작은 입력사례부터 먼저 해결하는 상향식 방법으로 전체 입력사례에 대한 해답을 구한다.

 

이항계수 구하기

 

이항계수 (binomial coefficient)는 다음과 같다.

 

$$\left(\begin{array}{c}n\\ k\end{array}\right) = \frac{n!}{k!(n-k)!} \;\; \mathrm{for} \;\;0 \leq k \leq n$$

 

위의 식을 이용해 이항계수를 구할 때, $n$이나 $k$가 값이 큰 경우 구하는 값이 너무 커지기 때문에 구하기 힘들다. 그래서 재귀 관계식을 이용한다.

 

재귀 관계식은 다음과 같다.

 

$$\left(\begin{array}{c}n\\ k\end{array}\right) = \begin{cases} \left(\begin{array}{c}n-1\\ k-1\end{array}\right) + \left(\begin{array}{c}n-1\\ k\end{array}\right) & 0<k<n\\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;1 & k=0\; \mathrm{or} \;k=n\end{cases} $$

 

분할정복으로 이항계수 구하기

 

입력 : $ k \leq n$을 만족하는 $0$ 이상의 정수 $n$과 $k$

출력 : bin, 이항 계수 $\left(\begin{array}{c}n\\ k\end{array}\right)$

 

int bin(int n, int k){
  if(k == 0 || n == k) return 1;
  else return bin(n-1, k-1) + bin(n-1, k);
}

 

위의 알고리즘은 매우 비효율적이다. 위의 알고리즘이 계산하는 항의 개수는 다음과 같다.

 

$$2\left(\begin{array}{c}n \\ k \end{array}\right) - 1$$

 

위의 식 증명은 다음과 같다.

 

$$T(n,k) = 2 \begin{bmatrix} n \\ k \end{bmatrix} - 1 $$

 

Induction Basis :

 

$\mathrm{if} \; n=1, \;\;2\begin{bmatrix}n \\ k \end{bmatrix} -1  = 2 \times 1 - 1 = 1$

 

Induction Hypothesis :  위의 식이 사실이라고 가정하자.

 

Induction Step :  $\begin{bmatrix} n+1 \\ k \end{bmatrix}$를 계산한다.

 

$\begin{eqnarray} T(n+1,k) & = & T(n,k-1) + T(n,k) + 1 \\ & = & \begin{bmatrix} n \\ k-1 \end{bmatrix} - 1 + 2 \begin{bmatrix} n \\ k \end{bmatrix} -1 + 1 \\ & = & 2 \begin{bmatrix} n+1 \\ k \end{bmatrix} -1 \end{eqnarray} $

 

 

재귀 호출할 때마다 같은 사례를 중복으로 계산한다. 이 과정에서 엄청난 비효율이 항상 발생할 수밖에 없다.

시간 복잡도도  $O(n!)$이기 때문에 좋은 알고리즘이 아니다.

효율적인 알고리즘을 동적계획을 설계하자.

 

동적계획으로 이항계수 구하기

 

위에서 구한 재귀관계식으로 배열 $DP[i][j]에 \left(\begin{array}{c} i \\ j \end{array}\right)$값을 차례로 저장한다.

 

동적계획 알고리즘을 작성하는 절차는 다음과 같다.

 

1, 재귀 관계식을 세운다.

 

$$ DP[i][j] = \begin{cases} DP[i-1][j-1] + DP[i-1][j] & 0<j<i \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; 1 & j=0 \; \mathrm{or} \;j = i  \end{cases} $$

 

2. 첫째 행부터 $DP$의 행에 값들을 차례로 계산해 저장하는 상향식 방식으로 문제를 푼다.

 

int bin2 (int n, int k){
  int i, j;
  int DP[n][k];

  for(int i=0;i<=n;i++){
    for(int j=0;j<=min(i,k);j++){
      if(j==0 || j==i) DP[i][j] = 1;
      else DP[i][j] = DP[i-1][j-1] + DP[i-1][j];
    }
  }
  return DP[n][k];
}

 

각 $i$값에 대해 $\mathrm{for} - j $ 루프를 몇번 실행하는지 보자.

$i$	$0\;1\;2\;3 \;\;\;\;\; \cdots \;\;\;\;\; k \;\;\;\;\; k+1 \;\;\;\;\; \cdots \;\;\;\;\; n$
루프 실행 횟수	$0\;1\;2\;3 \;\;\;\;\; \cdots \;\;\;\;\; k \;\;\;\;\; k+1 \;\;\;\;\; \cdots \;\;\;\;\; k+1$

 

따라서 총 실행 횟수는 다음과 같다.

 

$$ 1+2+3+4+ \cdots + k +\underbrace{(k+1)+(k+1)+\cdots +(k+1)}_{n-k+1} $$

 

위 결과를 계산하면 다음 등식을 얻는다.

 

$$ \frac{k(k+1)}{2} + (n-k+1)(k+1) = \frac{ (2n-k+2)(k+1) }{ 2 } \in \Theta (nk) $$

 

위의 분할정복보다 동적계획으로 훨씬 더 효율적인 알고리즘을 설계했다. 

 

둘의 차이점은 동적계획은 맹목적으로 재귀를 적용하는 대신 재귀관계식을 사용해 작은 입력사례부터 시작해 반복적으로 입력사례의 해답을 구해나간다는 것이다. 이러면 중복을 방지할 수 있다.

 

 

플로이드 와샬 알고리즘

 

플로이드 와샬 알고리즘은 여러가지 마디(vertex) 각각의 최단 경로를 구하는 알고리즘이다.

 

우선, 최단 경로를 구하는 알고리즘 중 가장 쉽게 푸는 알고리즘은 각 마디에 대해서 그 마디에서 다른 각 마디로 가는 모든 경로의 길이를 구한 후, 그 길이 중에서 최소 값을 찾는 것인데, 이 알고리즘은 지수시간(exponential)보다도 오래 걸린다. 

 

위의 알고리즘에서 찾는 경로의 개수는 다음과 같다.

 

$$ (n-2)(n-3) \cdots 1 = (n-2)! $$

 

Sterling's formula

$$n! \simeq \sqrt{2 \pi n} ( \frac{n}{e} )^ n  $$

$$n! \in \Theta(n^n) \;\;\;\; a^n < n^n $$

 

위의 값은 지수보다 큰 수이다. 이보다 효율적인 알고리즘인 플로이드 와샬 알고리즘을 살펴보자

 

플로이드 와샬 알고리즘을 사용하면, 최단 경로 문제를 푸는 시간복잡도가 $O(n^3)$인 알고리즘을 만들어 낼 수 있다.

 

$n$개 마디로 된 가중치포함 그래프는 다음과 같이 배열 $W$로 표현한다.

 

$$W[i][j] = \begin{cases} 이음선 \; 가중치 & v_i에서\; v_j로\; 가는 \;이음선이 \;있는\; 경우 \\ \infty & v_i에서\; v_j로\; 가는 \;이음선이 \;없는\; 경우 \\ 0 & i=j \end{cases} $$

 

여기서 새로운 배열 $D^{(k)}$을 만든다. 여기서 $0 \leq k \leq n$이고, $D^{(k)}$는 다음과 같이 정의한다.

 

$$D^{(k)}[i][j] = 집합 \{v_1,\;v_2,\;\cdots, \; v_k \}에 \;속하는 \; 마디만을 \; 거쳐서 \; v_i에서 \; v_j로 \; 가는 \; 최단경로의 \; 길이 $$

 

가중치포함 방향그래프 예시

$W$	1	2	3	4	5
1	0	2	3	1	10
2	$\infty$	0	$\infty$	2	$\infty$
3	8	$\infty$	0	1	1
4	$\infty$	$\infty$	$\infty$	0	3
5	7	4	$\infty$	$\infty$	0

 

$D$	1	2	3	4	5
1	0	2	3	1	4
2	12	0	15	2	5
3	8	5	0	1	1
4	10	7	13	0	3
5	7	4	10	6	0

 

$W$는 위의 가중치포함 방향그래프를 나타내고, $D$는 최단경로의 길이를 나타낸다. 최단경로를 푸는 알고리즘은 $W$에 있는 값을 가지고 $D$에 있는 값을 계산한다.

 

위의 예시 그래프를 가지고 $D^{(k)}[i][j] $ 값을 계산하는 예시를 살펴보자.

 

$D^{(0)}[2][5] = length[v_2][v_5] = \infty $

$\begin{eqnarray} D^{(1)}[2][5] &= &minumum(length[v_2 , v_5], length[v_2, v_1, v_5] ) \\ & = & minimum( \infty, \infty) = \infty \end{eqnarray}$

$D^{(2)}[2][5] = D^{(1)}[2][5] = \infty$

$D^{(3)}[2][5] = D^{(2)}[2][5] = \infty$

$\begin{eqnarray} D^{(4)}[2][5] &= &minimum(length[v_2,v_4,v_5], length[v_2, v_1, v_5]) \\ & = & minimum( 5, \infty) = 5 \end{eqnarray}$

$D^{(2)}[2][5] = D^{(4)}[2][5] = 5$

 

1. 이런 방식으로 $D^{(k-1)}$로부터 $D^{(k)}$를 계산하는 재귀 관계식을 정립한다.

2. $k =1 $ 부터 $n$까지 (절차 1에서 정립한) 과정을 상향식으로 반복해 문제를 해결한다.

 

$$D^0(=W),\;D^1,\;D^2,\;\cdots,D^n (=D)$$

 

위의 절차 1을 실행하기 위해선 두 가지 경우를 고려해야한다.

 

경우 1.

 

${v_1, v_2, \cdots, v_k}$에 속한 마디만 중간 마디로 거쳐서 $v_i$에서 $v_j$로 가는 최단경로 중에서 최소한 하나는 $v_k$를 거치지 않는 경우

 

이때, 다음과 같은 식이 성립한다. 

 

$$D^{(k)}[i][j] = D^{(k-1)}[i][j]$$

 

경우 2.

 

${v_1, v_2, \cdots, v_k}$에 속한 마디만 중간마디로 거쳐서 $v_i$에서 $v_j$로 가는 최단경로는 모두 $v_k$로 거치는 경우

 

이때, 다음과 같은 식이 성립한다.

 

$$D^{(k)}[i][j] = D^{(k-1)}[i][k] + D^{(k-1)}[k][j] $$

 

$$D^{(k)}[i][j] = minimum(\underbrace{D^{(k-1)}[i][j]}_{경우\; 1}, \underbrace{D^{(k-1)}[i][k] + D^{(k-1)}[k][j]}_{경우 \; 2}) $$

 

위의 절차에서 정립한 과정을 $k=1$부터 $n$까지 상향식으로 계속 반복해주면 된다.

 

void floyd (int n, const int W[][], int D[][]) {
  int i,j,k;
  D = W;
  for(k=1;k<=n;k++)
    for(i=1;i<=n;i++)
      for(j=1;j<=n;j++)
        D[i][j] = min(D[i][j], D[i][k] + D[k][j]);
}

프로이드 알고리즘 의사 코드

 

반응형

일정 시간복잡도 분석

 

단위연산 : for-루프안의 명령문

입력크기 : $n$(그래프에서 마디의 개수)

 

루프가 3개가 중첩되어있고, 이 루프는 각각 $n$번씩 실행한다. 

 

$$T(n) = n \times n \times n \in \Theta(n^3) $$

 

최단 경로 출력

 

$$P[i][j] = \begin{cases} v_i와 \; v_j의 \; 최단경로 \; 사이에서 \; 가장 \; 큰 \; vertex \; 인덱스\; 값 & 사이에 \; 최소 \; 하나의 \; vertex가 \; 있는 \; 경우  \\ 0 & 사이에 \; vertex가 \; 없는 \; 경우   \end{cases} $$

 

최단 경로를 출력해주려면 우선 위의 플로이드 알고리즘 코드에 위의 새로운 행렬 P를 추가해주어야한다.

 

void floyd (int n, const int W[][], int D[][], int P[][]) {
  int i,j,k;
  
  for(i=1;i<=n;i++)
  	for(j=1;j<=n;j++)
    	P[i][j] = 0;
        
  D = W;
  
  for(k=1;k<=n;k++){
    for(i=1;i<=n;i++) {
      for(j=1;j<=n;j++) {
        if(D[i][k] + D[k][j] < D[i][j]) {
        	P[i][j] = k;
        	D[i][j] = D[i][k] + D[k][j];
        }
}

최단경로를 구하기 위해 변형한 프로이드 알고리즘 의사코드

 

void path (int q, r)
{
	if(P[q][r] != 0){
    	path(q, P[q][r]);
        cout << "v" << P[q][r];
        path(P[q][r], r);
}

최단 경로 출력 의사 코드

 

배열 P가 최단 경로에 있는 가장 큰 vertex의 인덱스 값을 저장하기 때문에 재귀 함수를 이용해 계속해서 0이 아니면 탐색하는 방식을 활용하면 경로를 출력할 수 있다.

 

최적화 원리 (principle of optimality)

 

어떤 문제의 입력사례의 최적해가 그 입력사례를 분할한 부분사례에 대한 최적해를 항상 포함하고 있으면, 그 문제는 최적화 원리가 성립한다고 한다.

 

최장거리를 구할 때는 최적화 원칙이 적용되지 않는다.

 

https://kimmessi.tistory.com/98

[플로이드-와샬] BOJ 11404 플로이드

 

플로이드 문제의 풀이

연쇄 행렬곱셈(chained matrix multiplication)

 

$i \times j$행렬과 $j \times k$행렬을 곱하면 원소단위 곱셈의 실행 횟수는 다음과 같다.

 

$$i \times j \times k $$

 

예를 들어 $A_1 \times A_2 \times A_3$ 행렬들을 곱한다고 해보자.

이때, $A_1$는 $10\times 100$, $A_2$는 $100 \times 5$ 그리고 $A_3$는 $5 \times 500$이다.

 

$(A_1 \times A_2) \times A_3$

$\rightarrow 10\times 100 \times 5 + 10 \times 5 \times 50 = 7500$

 

$A_1 \times (A_2 \times A_3)$

$\rightarrow 100 \times 5 \times 50 + 10 \times 100 \times 5 = 75000$

 

이처럼 같은 결과가 나오지만 그 연산 횟수는 엄청난 차이가 난다.

 

행렬 곱셈의 최소한의 연산 횟수를 구하는 알고리즘을 구할 때, 다이나믹 프로그래밍을 사용해야 간단히 풀 수 있다.

 

1. 먼저 행렬의 행과 열에 겹치는 숫자들을 제거하기 위해 arr에 0열에 겹치지 않는 숫자들을 입력해준다.

 

2. 그 후 행렬끼리 곱할 때 생기는 단위 연산이 최소가 되게 다이나믹 프로그래밍기법을 이용하여 풀어준다.

 

$dp[i][j]$는 위에 arr의 arr[i][0]에서 arr[j][0]까지의 행렬 곱셈의 최소 연산 갯수를 나타낸다.

 

$$dp[i][j] = \begin{cases} dp[i][j] & = & minimum_{i \leq k \leq j-1} (dp[i][k] + dp[k+1][j] +d_{i-1}d_{k}d_{j}) \\ dp[i][i] & = & 0 \end{cases} $$

 

저 순서대로 $dp[i][j]$를 탐색하는데, 그래야 위로 올라가면서 위의 식에 해당하는 항들이 차례대로 구성되기 때문이다.

 

3. dp[1][N]을 출력한다.

 

아래는 위의 방법대로 푼 문제이다.

https://kimmessi.tistory.com/70

[DP] BOJ 11049 행렬 곱셈 순서

 

단위연산 총 실행 횟수

 

세번째 for문 $j-1-i+1 = i+diagonal -1-i+1 = diagonal$

 

$\sum_{diagonal = 1}^{n-1} [(n - diagonal) \times diagonal]$

 

위의 식을 풀면 

 

$ \frac{n(n-1)(n+1)}{6} \in \Theta(n^3) $