동적 계획법(4) - 행렬 곱 & LCS

Dynamic Programming (4)

행렬의 곱샘

- p x q 행렬 A와 q x r 행렬 B를 곱한다.

void product (int[][] A, int[][] B, int[][] C) {

for (int i = 0; i < p; i++) {

for (int j = 0; j < r; j++) {

C[i][j] = 0;

for (int k = 0; k < q; k++) {

C[i][j] += A[i][k] * B[k][j];

}

}

}

-> 이 코드에서 곱셈연산의 횟수는 pqr이 된다.

Matrix-Chain 곱하기

- 행렬 A는 10 X 100, B는 100 X 5, C는 5 X 50행렬이다.

- 세 행렬의 곱 ABC는 두 가지 방법으로 계산할 수 있다. (결합법칙이 성립한다.)

(AB)C : 7500번의 곱셈 필요 (10 X 100 X 5 + 10 X 5 X 50)

A(BC) : 75000번의 곱셈 필요 (100 X 5 X 50 + 10 X 100 X 50)

- 곱하는 순서에 따라서 연산량이 크게 달라질 수 있다.

- n개의 행렬의 곱 $A_1A_2a_3$...$A_n$을 계산하는 최적의 순서는 쉽게 나오지 않는다는 것을 알 수 있다.

- 위 예시의 $A_i$는 $p_{k-1}$ X $p_k$행렬이다.

행렬 곱 - Optimal Substructure

행렬 곱 - 순환식

- m[i, j] : $A_iA_{i+1}$ ... $A_j$를 곱하는 최소 곱셈의 횟수, i는 j보다 작거나 같다

- i보다 j가 클 때 i부터 k까지의 최적 계산량에 k+!부터 j까지의 최적 계산량을 더하고 i와 j를 곱하는 비용까지 전부 더한 값중 최소값을 찾으면 최적 계산 결과가 나온다.

i보다 j가 크거나 같기를 바라기 때문에 회색 부분은 필요 없이 버리게 된다. 행렬에서 (1, 8)의 부분은 최소 값으로 계산식을 통해 최종적으로 찾아내고 싶은 결과이다.

계산 횟수는 1에서 2, 3으로 올라갈수록 하나씩 줄어들어간다.

행렬 곱 - BottomUp방식

int matrixChain (int n) {

for (int i = 1; i <= n; i++)

m[i][i] = 0;

for (int r = 1; r <= n - 1; r++) { // n - 1개

for (int i = 1; i <= n - r; i++) { // 각 대각선들의 값 개수

// r번째 대각선의 i번째 값을 계산한다.

int j = i + r;

m[i][j] = m[i + 1][j] + p[i - 1] * p[i] * p[j];

for (int k = i + 1; k <= j - 1; k++) {

if (m[i][j] > m[i][k] + p[k + 1][j] + p[i - 1] * p[i] * p[j])

m[i][j] = m[i][k] + p[k + 1][j] + p[i - 1] * p[i] * p[j];

}

}

}

return m[1][n];

}

-> 위 식의 시간 복잡도는 Θ($n^3$)이 된다.

Longest Common Subsequence(LCS문제)

- 입력으로 두개의 문자열이 주어진다.

- <bcdb>는 문자열<abcbdab>의 subsequence이다.

- <bca>는 문자열 <abcbdab>와 <bdcaba>의 common subsequence이다.

- Longest common subsequence (LCS)

common subsequence들 중 가장 긴 문자열을 뜻한다.

Ex) <bcba>는 Mabcbdab>와 <bdcaba>의 LCS라고 할 수 있다.

LCS 해결법 - Brute Force

- 문자열 x의 모든 subsequence에 대해 그것이 y의 subsequence가 되는지 검사한다.

- |x| = m, |y| = n

- x의 subsequence가 되는 개수 = $2^m$

- 각각이 y의 subsequence가 되는지 검사하는데 걸리는 시간 : O(n)

- 총 시간 복잡도 : O(n$2^m$)

LCS - Optimal Substructure

- 순환적인 구조를 띈다는 것을 쉽게 찾아낼 수 있다.

LCS 해결법 - 순환식

- L[i, j] : 문자열 X = <$x_1x_2$ ... $x_i$>와 Y = <$y_1y_2$ ... $y_j$> 사이 LCS의 길이

- 문제를 푸는 과정에서 위 그림의 A, 곧 밑에서의 $X_i$와 $Y_j$를 포기하고 계산할 이유가 없다는 것을 알 수 있다.

- case 1 : $x_i$ = $y_j$

L[i, j] = L[i - 1, j - 1] + 1

- case 2 : $x_i$ ≠ $y_j$

L[i, j] = max(L[i, j - 1], L[i - 1, j])

- 최종적으로 도출되는 경우들의 계산법은 아래와 같다.

- 순환식을 통한 계산 과정

- LCS 구현 코드

행 우선 순서로 진행되는 코드이다.

int lcs (int m, int n) { //m은 x의 길이, n은 y의 길이이다.

for (int i = 0; i <= m; i++)

c [i][0] = 0;

for (int j = 0; j <= n; j++)

c[0][j] = 0;

for (int i = 0; i <= m; i++) { // 행

for (int j = 0; j <= n; j++) { // 열

if (x[i] == y[j])

c[i][j] = c[i - 1][j - 1] + 1;

else

c[i][j] = Math.max(c[i - 1][j], c[i][j - 1]);

}

}

return c[m][n];

}

-> 위 코드의 시간 복잡도는 Θ(mn)이 된다.