matrix chain
행렬의 곱셈
행렬의 곱셈
행렬의 곱셈은 아래와 같이 이루어진다.
행렬 A (p, q) * 행렬 B (q, r) = 행렬 C(p, r)
즉, A행렬의 열의 길이와 B행렬의 행의 길이가 같아야만 행렬 간 곱셈이 성립될 수 있고, 계산한 결과 행렬 C는 행의 길이가 p이고, 열의 길이가 r인 행렬이 된다.
이때, 연산의 횟수는 p*q*r 이 된다.
행렬의 곱셈에서는 교환법칙이 성립하지 않는다. 행렬 A와 B 간에 곱셈을 하기 위해서는 각각의 열과 행의 길이가 위에서 말한 것처럼 맞아야 하므로, AB = BA 를 반드시 보장할 수 없고, 어쩌면 교환법칙을 할 경우, 행렬의 곱셈 자체가 불가능해질수도 있다.
하지만 결합법칙은 성립할 수 있다. 행렬이 3개 이상 곱해진다고 생각해보면, (AB)C = A(BC) 는 충분히 성립할 수 있다. 각각의 열과 행의 길이가 맞다는 것이 보장되기 때문이다.
Matrix-Chain, 세개 이상 행렬의 곱셈
이렇게 세 개 이상의 행렬이 곱셈을 할 때, 결합법칙에 따라 연산 순서를 바꿀 수 있는데, 이 경우, 각각의 케이스마다 연산 횟수가 눈에 띄게 달라질 수 있다.
예를 들어, 아래와 같다고 가정해보면,
행렬 A 10 * 100
행렬 B 100 * 5
행렬 C 5 * 50
(AB)C = 10*100*5 + 10*5*50 = 7,500 번의 연산
A(BC) = 100*5*50 + 10*100*50 = 75,000 번의 연산
연산 순서만 다르게 했을 뿐인데, 연산의 횟수가 10배나 차이가 나게 된다.
따라서 matrix-chain 유형의 문제에서는 여러개의 행렬 곱셈에 대하여 어떤 연산 순서로 진행을 해야 가장 적거나 많은 연산을 하게 되는지 구하는 문제들이 출제가 된다.
n개의 행렬의 곱 A1A2A3 ... An을 계산하는 최적의 순서는? (이때, Ai는 Pk-1 * Pk)
optimal substructure
행렬의 곱셈 결과는 결국 행렬의 형태를 띈다.
행렬 z를 구하려면, 결국 행렬 x와 y의 곱을 해야한다. 그리고 행렬에서는 교환법칙이 성립하지 않기 때문에 이 x와 y는 1부터 k까지의 곱, k+1부터 n까지의 곱의 결과가 된다.
결국 두 행렬의 곱에 대해서는 위와 같은 순환식을 만들 수 있을 것이다.
Ai부터 Aj까지의 행렬을 곱하는데 최소로 곱셈 연산을 하는 횟수를 구하려면,
i부터 임의의 지점 k까지의 최소 연산 횟수와
k+1부터 j까지의 최소 연산횟수를 더하고,
두 결과의 연산 횟수인 pi-1 * pk*pj 를 곱한 값을 더해야한다.
설명) Ai = pi-1 * pk, Aj = pk * pj 이므로 위와 같이 된다.
이때, base case는 아래와 같은 논리로 구한다.
결국, 행렬의 곱셈식 중에서 중간에 임의의 k값을 정하고 앞 뒤로 연산한 결과값을 더하는 연산이 반복된다는 것을 발견
연산을 거듭할수록 i와 j는 서로 같아지게 될 것이다. 이것이 base case 가 된다.
i = j인 경우, 행렬 1개에 대해서 곱셈 연산의 최소 횟수는 아예 하지 않는 경우이므로, 0이 된다.
그러면 이제 순환식을 계산하는 순서를 정해야한다. 이전 연산의 해가 다음 연산의 재료로 이용되기 위해서는 어떤 순서로 계산을 해야할까?
순환식을 분석해보면 되는데,
우선은 i <= j 이므로, m[i, k] 는 m[i, i], m[i, i+1], m[i, i+2], ... m[i, j-1] 까지의 값을 알아야 한다.
m[k+1, j] 의 경우는 m[i+1, j], m[i+2, j], m[i+3, j], ..., m[j, j] 까지의 값을 알아야 한다.
그렇다면 이 경우에는 기존처럼 행 우선 연산을 이용할 수는 없고, 두 가지의 순서를 생각해볼 수 있다.
하나는 밑에서 위로 왼쪽부터 오른쪽으로 계산하는 경우와
또 다른 하나는 대각선으로부터 시작하여 점차 우상향하는 방법이 있다.
사실 코딩하기에는 밑에서 위로 계산하는 방법이 쉬운데, 대부분의 예제에서는 대각선으로 구현한 것이 많이 등장한다.
코드로 구현해보자면 위와 같다. 먼저 대각선을 모두 0으로 채운다.
그다음 대각선을 우상향하는 방향으로 1부터 n-1 까지 순회한다. 대각선의 개수가 (i, i) 대각선을 제외하고 n-1개라는 것을 기억한다.
i 좌표는 1부터 n-r까지 순회하는데, 각 대각선의 값의 개수만큼을 의미한다. 대각선부터 시작해서 점차 1개씩 줄어드는데, 대각선에서 값의 개수가 n개이므로, 총 n-r개만큼의 값을 점검하게 된다.
이때, j의 좌표값은 i 값에서 r만큼 이동한 위치가 되므로, i+r 이 된다.
(i, j)위치까지의 최소값 m[i, j]는 m[i, k] + m[k+1][j] 가 된다. 임의의 지점 k에 대하여 범위는
i<=k<=j-1이 성립하므로, 우선 k=i 라고 시작점을 둔 후, k=i+1 부터 k=j-1까지 차례대로 순회하며 최소값을 비교한다.즉 가장 최소값이 되는 임의의 지점 k를 구하기 위해서 i부터 j-1까지 모든 경우의 수를 검사하는 것이다.
Last updated
