[Algorithm] C++로 구현한 행렬 곱셈 알고리즘

[그림 1] 행렬의 곱셈

행렬의 곱셈 알고리즘은 여러 가지가 존재합니다.

이번 글에서는 행렬의 곱셈 방식과 이를 토대로 한 단순 곱셈 알고리즘을 유도해 보겠습니다.

---

$$ \begin{bmatrix}
 a_{11}&a_{12}&a_{13}\\
 a_{21}&a_{22}&a_{23}\\
\end{bmatrix}
\times
\begin{bmatrix}
b_{11} & b_{12} \\
b_{21} & b_{22} \\
b_{31} & b_{32} \\
\end{bmatrix} $$

 

위와 같은 행렬이 존재할 때, 앞의 행렬을 A, 뒤의 행렬을 B라고 하겠습니다.

행렬 A의 크기는 2*3이고, 행렬 B의 크기는 3*2입니다.

 

1. 행렬 곱셈의 조건

행렬 곱셈을 하기 위해서는 행렬 A의 열과 행렬 B의 행의 개수가 동일해야 합니다.

예시로 든 행렬은 행렬 A의 열과 행렬 B의 행의 개수가 모두 3으로 동일하기 때문에 곱셈이 가능합니다.

 

2. 연산 방법

$$ \begin{bmatrix}
a_{11}b_{11} + a_{12}b_{21} + a_{13}b_{31} & a_{11}b_{12} + a_{12}b_{22} + a_{13}b_{32} \\
a_{21}b_{11} + a_{22}b_{21} + a_{23}b_{31} & a_{21}b_{12} + a_{22}b_{22} + a_{23}b_{32}\\
\end{bmatrix} $$

계산을 하면 다음과 같이 (2 * 2) 크기의 행렬이 나오게 됩니다.

위 행렬을 행렬 C라고 하겠습니다.

 

행렬 곱셈의 결과는 무조건 (행렬 A의 행 개수 * 행렬 B의 열 개수)의 크기가 됩니다.

 

위 결과가 나오기까지의 순서입니다.

2-1. 하나의 성분 구하기

$$ \begin{bmatrix}
 \mathbf{a_{11}}& \mathbf{a_{12}}&\mathbf{a_{13}}  \\
 a_{21}&a_{22}&a_{23}  \\
\end{bmatrix}
\times
\begin{bmatrix}
 \mathbf{b_{11}}& b_{12} \\
 \mathbf{b_{21}}& b_{22} \\
 \mathbf{b_{31}}& b_{32} \\
\end{bmatrix}  $$

 

위 행렬의 bold체로 된 요소들을 이용해 행렬 C(1, 1)의 성분을 구하면 다음과 같습니다.

$$ a_{11}b_{11} + a_{12}b_{21} + a_{13}b_{31}  $$

 

행렬 A의 열과 행렬 B의 행의 요소들을 가져와서 곱한 후 모두 더하면 됩니다.

 

이 때, 위 요소들을 가져오는 작업을 행렬 A의 열의 개수(or 행렬 B의 행의 개수)만큼 하게 됩니다.

여기서는 행렬 A의 열의 개수가 3이므로 가져오는 것을 3번 반복했습니다.

2-2. 하나의 행 구하기

$$ \begin{bmatrix}
 \mathbf{a_{11}}& \mathbf{a_{12}}&\mathbf{a_{13}}  \\
 a_{21}&a_{22}&a_{23}  \\
\end{bmatrix}
\times
\begin{bmatrix}
 \mathbf{b_{11}}& \mathbf{b_{12}} \\
 \mathbf{b_{21}}& \mathbf{b_{22}} \\
 \mathbf{b_{31}}& \mathbf{b_{32}} \\
\end{bmatrix}  $$

위 행렬의 bold체로 된 요소들을 이용해 행렬 C의 첫 번째 행을 구하면 다음과 같습니다.

$$ \begin{bmatrix}
 a_{11}b_{11} + a_{12}b_{21} + a_{13}b_{31}&a_{11}b_{12} + a_{12}b_{22} + a_{13}b_{32}  \\
\end{bmatrix}  $$

 

위 연산은 2-1의 연산을 행렬 B의 열의 개수만큼 반복한 것과 같습니다.

여기서는 행렬 B의 열의 개수가 2이므로 2번 반복해서 결과가 나왔습니다.

 

2-3. 최종 결과 구하기

$$ \begin{bmatrix}
 a_{11}& a_{12}&a_{13}  \\
 a_{21}&a_{22}&a_{23}  \\
\end{bmatrix}
\times
\begin{bmatrix}
 b_{11}& b_{12} \\
 b_{21}& b_{22} \\
 b_{31}& b_{32} \\
\end{bmatrix} 
=
\begin{bmatrix}
 a_{11}b_{11} + a_{12}b_{21} + a_{13}b_{31}&a_{11}b_{12} + a_{12}b_{22} + a_{13}b_{32}  \\
 a_{21}b_{11} + a_{22}b_{21} + a_{23}b_{31}&a_{21}b_{12} + a_{22}b_{22} + a_{23}b_{32}  \\
\end{bmatrix} $$

 

2-2의 연산을 행렬 A의 행의 개수만큼 반복하면 최종 결과가 나옵니다.

여기서는 행렬 A의 행의 개수가 2이므로 2번 반복해서 결과가 나왔습니다.

 

3. 알고리즘 유도

위의 연산 순서를 통해 다음과 같은 반복문을 작성할 수 있습니다.

[그림 2] 행렬 곱셈 반복문

시간 복잡도가 \( O(n^3) \)인 반복문이 만들어집니다.

위 반복문을 토대로 코드를 작성하면 됩니다.

 

4. 코드 작성

위의 순서를 토대로 C++로 작성한 코드입니다.

#include <iostream>
using namespace std;

/* 행렬 길이 상수 정의 */
#define A_col  2
#define A_row  3
    
#define B_col  3
#define B_row  2

int main() {
    
    /* 행렬 정의 */
    int A[2][3] = {{ 3, 1, -5},
                    { 6, -2, 4}};
                   
    int B[3][2] = {{ 5, -1},
                    { 3, 6},
                    {-8, 7}};
                   
    int C[A_col][B_row] = {{0, 0},
                            {0, 0}};
    
    /* 행렬 곱셈 조건 확인 */
    if (A_row != B_col) { cout << "error" <<'\n'; return 0; } // 조건이 되지 않으면 프로그램 종료
    
    /* 행렬 곱셈 연산 */
    for(int i = 0; i < A_col; i++) {
        for(int j = 0; j < B_row; j++) {
            int sum = 0;
            // for(int k = 0; j < B_col; k++)도 가능. 어짜피 똑같음
            for(int k = 0; k < A_row; k++) {
                sum += A[i][k] * B[k][j];
            }
            C[i][j] = sum;
        }
    }
    
    /* 결과 출력 */
    for(int i = 0; i < A_col; i++) {
        for(int j = 0; j < B_row; j++) {
            cout << C[i][j] << ' ';
        }
        cout << '\n';
    }
}

 

Python으로 작성한 코드는 다음 게시물을 참고하기 바랍니다.

https://spareone.tistory.com/70

[PS] 백준 2740번 - 행렬 곱셈 | Python