[알고리즘 Tip] 행렬의 곱셈

갑자기 행렬의 곱셈은 왜?

---

모 회사 코딩테스트에서 행렬의 곱 성질을 이용해 2차원 배열을 연산하는 문제가 나왔다.

이미 행렬의 곱셈 방법은 알고 있었지만, 막상 코드로 구현하려니 단번에 생각나지 않았다.

자꾸 코드를 쓰다가 지우고 쓰다가 지우고 하며 '어, 이게 아니네?'라고 생각하기 일쑤였다.

그래서 아예 행렬 곱셈 기본 틀을 기억하기 위해 포스팅을 결심했다.

행렬의 곱셈 : 기본 성질

---

우선 개념부터 다시 정리.

1. 앞 행렬의 열의 개수와 뒷 행렬의 행의 개수가 같아야 한다. (ex. 2x3 X 3x4 : 가능 / 2x2 X 3x2 : 불가)

2. 정답 행렬은 앞 행렬의 행의 개수 X 뒷 행렬의 열의 개수이다. (ex. 2x3 X 3x4 = 2x4)

아래 그림과 같다.

행렬의 곱셈 : 실전 코드

---

행렬의 곱셈은 일반적으로 아래처럼 삼중 loop문으로 구현할 수 있다.

int[][] answer = new int[A.length][B[0].length];
 
for(int i = 0; i < A.length; i++) {
    for(int j = 0; j < B[0].length; j++) {
        int m = 0;
        while(m < A[0].length) {
            answer[i][j] += A[i][m] * B[m][j];
            m++;
        }
    }
}

따라서 시간복잡도는 빅오표기법으로 이다.

세제곱은 input에 따라 그 양이 기하급수적으로 증가하기 때문에, 이를 개선하는 알고리즘도 있다.

분할 정복이나 Strassen Algorithm을 이용하면 시간복잡도를 줄일 수 있다.

이 내용은 나중에 다루겠다.