행렬 곱셈 알고리즘 완벽 정리: 원리부터 C++ 구현 예제까지

이 글에서는 두 행렬을 곱하는 방법, 즉 행렬 곱셈(Matrix Multiplication) 알고리즘에 대해 자세히 살펴보겠습니다.

행렬 곱셈의 기본 조건

행렬 곱셈은 모든 행렬에 대해 항상 가능한 것은 아니며, 반드시 다음 조건을 만족해야만 수행할 수 있습니다.

두 행렬 A와 B가 있고, 각각의 크기(차원)가 A는 m×n, B는 p×q라고 가정해 봅시다. 이때 두 행렬의 곱은 첫 번째 행렬 A의 열(column) 개수 n과 두 번째 행렬 B의 행(row) 개수 p가 같을 때, 즉 n = p인 경우에만 계산할 수 있습니다.

조건이 만족되면 결과 행렬 C의 크기는 m×q가 됩니다. 즉, 결과 행렬의 행 개수는 첫 번째 행렬의 행 개수를, 열 개수는 두 번째 행렬의 열 개수를 따르게 됩니다.

알고리즘 의사코드(Pseudocode)

행렬 곱셈의 전체적인 흐름은 아래 의사코드와 같습니다. 세 개의 중첩 반복문을 사용하여 결과 행렬의 각 원소를 계산합니다.

matrixMultiply(A, B):
A의 차원이 (m x n), B의 차원이 (p x q)라고 가정
시작
    if n ≠ p 이면 종료   // 곱셈 불가능
    그렇지 않으면 결과 행렬 C를 (m x q)로 정의
    for i = 0 부터 m-1 까지 반복:
        for j = 0 부터 q-1 까지 반복:
            for k = 0 부터 p-1 까지 반복:
                C[i, j] = C[i, j] + (A[i, k] * B[k, j])
종료

여기서 핵심은 결과 행렬 C의 (i, j) 위치 원소가 행렬 A의 i번째 행과 행렬 B의 j번째 열에 해당하는 원소들을 순서대로 곱한 뒤 모두 더한 값이라는 점입니다.

시간 복잡도

세 개의 중첩 반복문을 사용하므로, 일반적인 행렬 곱셈 알고리즘의 시간 복잡도는 O(m × q × p)입니다. 두 행렬이 모두 n×n 크기의 정방행렬(square matrix)일 경우 O(n³)이 됩니다.

C++ 구현 예제

다음은 위 알고리즘을 C++로 구현한 코드입니다. 3×3 크기의 두 행렬을 곱하고, 곱셈 전에 차원 조건(c1 == r2)을 검사합니다.

#include<iostream>
using namespace std;
int main() {
    int product[10][10], r1=3, c1=3, r2=3, c2=3, i, j, k;
    int a[3][3] = {
        {2, 4, 1},
        {2, 3, 9},
        {3, 1, 8}
    };
    int b[3][3] = {
        {1, 2, 3},
        {3, 6, 1},
        {2, 4, 7}
    };
    if (c1 != r2) {
        cout<<"첫 번째 행렬의 열 개수는 두 번째 행렬의 행 개수와 같아야 합니다";
    } else {
        cout<<"첫 번째 행렬:"<<endl;
        for(i=0; i<r1; ++i) {
            for(j=0; j<c1; ++j)
                cout<<a[i][j]<<" ";
            cout<<endl;
        }
        cout<<endl;
        cout<<"두 번째 행렬:"<<endl;
        for(i=0; i<r2; ++i) {
            for(j=0; j<c2; ++j)
                cout<<b[i][j]<<" ";
            cout<<endl;
        }
        cout<<endl;
        // 결과 행렬 초기화
        for(i=0; i<r1; ++i)
            for(j=0; j<c2; ++j) {
                product[i][j] = 0;
            }
        // 행렬 곱셈 수행
        for(i=0; i<r1; ++i)
            for(j=0; j<c2; ++j)
                for(k=0; k<c1; ++k) {
                    product[i][j]+=a[i][k]*b[k][j];
                }
        cout<<"두 행렬의 곱:"<<endl;
        for(i=0; i<r1; ++i) {
            for(j=0; j<c2; ++j)
                cout<<product[i][j]<<" ";
            cout<<endl;
        }
    }
    return 0;
}

실행 결과

위 프로그램을 실행하면 다음과 같은 출력을 확인할 수 있습니다.

첫 번째 행렬:
2 4 1
2 3 9
3 1 8
두 번째 행렬:
1 2 3
3 6 1
2 4 7
두 행렬의 곱:
16 32 17
29 58 72
22 44 66

마무리

행렬 곱셈은 선형대수학의 기본 연산일 뿐만 아니라, 그래프 경로 탐색, 이미지 처리, 머신러닝 등 다양한 분야에서 활용되는 중요한 알고리즘입니다. 핵심은 차원 호환 조건(n = p)을 먼저 확인하고, 세 중첩 반복문을 통해 결과 행렬의 각 원소를 올바르게 계산하는 것입니다. 이 예제를 직접 실행해 보면서 행과 열의 인덱스가 어떻게 대응되는지 익혀두면 좋습니다.