두 개의 행렬 A와 B가 주어졌을 때, 두 행렬의 곱 AB를 계산해야 합니다. 이때 A의 열 개수는 B의 행 개수와 같다고 가정할 수 있습니다.
예를 들어 입력이 [[1,0,0],[-1,0,3]]과 [[7,0,0],[0,0,0],[0,0,1]]이라면,
| 1 | 0 | 0 |
| -1 | 0 | 3 |
| 7 | 0 | 0 |
| 0 | 0 | 0 |
| 0 | 0 | 1 |
출력은 [[7,0,0],[-7,0,3]]이 됩니다.
| 7 | 0 | 0 |
| -7 | 0 | 3 |
알고리즘 접근 방법
희소 행렬(sparse matrix)은 대부분의 원소가 0으로 채워져 있는 행렬을 의미합니다. 모든 원소를 순회하며 곱하는 대신 0이 아닌 원소만 미리 저장해 두면, 값이 0인 위치에 대한 불필요한 곱셈 연산을 건너뛸 수 있어 실행 속도가 크게 향상됩니다.
다음 단계에 따라 문제를 해결할 수 있습니다.
r1 := A의 행 개수, r2 := B의 행 개수
c1 := A의 열 개수, c2 := B의 열 개수
r1 × c2 크기의 2차원 배열 ret을 정의합니다(모든 원소는 0으로 초기화).
A의 각 행에서 0이 아닌 원소만 (열 인덱스, 값) 쌍으로 저장하기 위한 배열 sparseA[r1]을 정의합니다.
i := 0부터 시작해 i < r1인 동안 i를 1씩 증가시키며 반복합니다.
j := 0부터 시작해 j < c1인 동안 j를 1씩 증가시키며 반복합니다.
A[i, j]가 0이 아니라면:
sparseA[i]의 끝에 { j, A[i, j] }를 삽입합니다.
다시 i := 0부터 시작해 i < r1인 동안 i를 1씩 증가시키며 반복합니다.
j := 0부터 시작해 j < sparseA[i]의 크기인 동안 j를 1씩 증가시키며 반복합니다.
k := 0부터 시작해 k < c2인 동안 k를 1씩 증가시키며 반복합니다.
x := sparseA[i, j]의 첫 번째 요소(저장된 열 인덱스)
B[x, k]가 0이 아니라면:
ret[i, k] := ret[i, k] + sparseA[i, j]의 두 번째 요소 × B[x, k]
ret을 반환합니다.
일반적인 행렬 곱셈의 시간 복잡도는 O(r1 × c1 × c2)입니다. 반면 위 방식은 내부 연산이 0이 아닌 원소의 개수에 비례하므로, 행렬이 희소할수록 실제 연산량이 크게 줄어드는 장점이 있습니다.
C++ 구현 예시
더 나은 이해를 위해 다음 구현 코드를 살펴보겠습니다.
class Solution {
public:
vector<vector<int>> multiply(vector<vector<int>>& A, vector<vector<int>>& B) {
int r1 = A.size();
int r2 = B.size();
int c1 = A[0].size();
int c2 = B[0].size();
vector<vector<int>> ret(r1, vector<int>(c2));
vector<pair<int, int>> sparseA[r1];
for(int i = 0; i < r1; i++){
for(int j = 0; j < c1; j++){
if(A[i][j] != 0)sparseA[i].push_back({j, A[i][j]});
}
}
for(int i = 0; i < r1; i++){
for(int j = 0; j < sparseA[i].size(); j++){
for(int k = 0; k < c2; k++){
int x = sparseA[i][j].first;
if(B[x][k] != 0){
ret[i][k] += sparseA[i][j].second * B[x][k];
}
}
}
}
return ret;
}
};
입력
{{1,0,0},{-1,0,3}},{{7,0,0},{0,0,0},{0,0,1}}
출력
[[7, 0, 0],[-7, 0, 3]]