이 글에서는 C++를 사용하여 두 개의 행렬을 곱하는 프로그램을 작성하는 방법을 알아보겠습니다.
행렬 곱셈은 선형대수학의 기본 연산 중 하나로, 그래픽 처리, 머신러닝, 과학 계산 등 다양한 분야에서 활용됩니다. 두 행렬이 주어졌을 때, 우리의 목표는 두 행렬의 곱을 계산하여 결과 행렬을 출력하는 것입니다.
행렬 곱셈의 기본 조건
두 행렬을 곱하려면 반드시 하나의 조건을 충족해야 합니다. 첫 번째 행렬의 열(column) 개수가 두 번째 행렬의 행(row) 개수와 같아야 합니다.
예를 들어, A가 m×n 크기의 행렬이고 B가 n×p 크기의 행렬이라면, A×B는 m×p 크기의 행렬이 됩니다. 결과 행렬의 각 요소는 첫 번째 행렬의 행과 두 번째 행렬의 열에 있는 요소들을 순서대로 곱한 후 모두 더한 값입니다.
C++ 구현 예제
아래는 4×4 크기의 두 정방행렬(square matrix)을 곱하는 전체 코드입니다.
#include <iostream>
using namespace std;
#define N 4
// 두 행렬의 요소들을 곱하여 결과 행렬에 저장
void calc_product(int mat1[][N], int mat2[][N], int res[][N]) {
int i, j, k;
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
res[i][j] = 0;
for (k = 0; k < N; k++)
res[i][j] += mat1[i][k] * mat2[k][j];
}
}
}
int main() {
int i, j;
int res[N][N];
int mat1[N][N] = {{1, 1, 1, 1},
{2, 2, 2, 2},
{3, 3, 3, 3},
{4, 4, 4, 4}};
int mat2[N][N] = {{1, 1, 1, 1},
{2, 2, 2, 2},
{3, 3, 3, 3},
{4, 4, 4, 4}};
calc_product(mat1, mat2, res);
cout << "Resultant matrix :\n";
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++)
cout << res[i][j] << " ";
cout << "\n";
}
return 0;
}코드 동작 원리
핵심 로직은 calc_product 함수에 있습니다. 이 함수는 세 개의 중첩된 반복문을 사용합니다.
- 바깥쪽 반복문(i): 결과 행렬의 각 행을 순회합니다.
- 중간 반복문(j): 각 행의 열을 순회합니다.
- 안쪽 반복문(k): 첫 번째 행렬의 i번째 행과 두 번째 행렬의 j번째 열에 해당하는 요소들을 곱하고 누적합니다.
즉, res[i][j]는 mat1[i][0]*mat2[0][j] + mat1[i][1]*mat2[1][j] + ... + mat1[i][N-1]*mat2[N-1][j]의 합으로 계산됩니다. 누적하기 전에 res[i][j] = 0;으로 초기화하는 것이 중요합니다.
실행 결과
Resultant matrix : 10 10 10 10 20 20 20 20 30 30 30 30 40 40 40 40
예를 들어 결과 행렬의 첫 번째 요소는 (1×1) + (1×2) + (1×3) + (1×4) = 10으로 계산되며, 나머지 요소들도 같은 방식으로 구해집니다.
시간 복잡도
이 알고리즘은 세 개의 중첩 반복문을 사용하므로 시간 복잡도는 O(N³)입니다. N이 커질수록 연산량이 급격히 증가하므로, 대규모 행렬 연산에는 스트라센(Strassen) 알고리즘과 같은 최적화 기법을 고려할 수 있습니다.