프로그래머스 - 행렬의 곱셈

programmers.co.kr/learn/courses/30/lessons/12949#

코딩테스트 연습 - 행렬의 곱셈

 

가장 단순한 방식으로 행렬의 곱셈을 구현하는 문제이다.

삼중 for문을 사용하면 구할 수 있다.

첫번째 for 문은 arr1 의 행 길이 만큼

두번째 for 문은 arr2 의 열 길이 만큼

세번째 for 문은 arr1 의 열 길이 만큼 돌면서

arr1[i][k] * arr2[k][j] 를 구하면 된다.

 

- c++

 

#include <string>
#include <vector>
 
using namespace std;
 
vector<vector<int>> solution(vector<vector<int>> arr1, vector<vector<int>> arr2) {
    int row = arr1.size(), col = arr2[0].size();
    vector<vector<int>> answer(row, vector<int>(col, 0));
    
    for (int i = 0; i < row; ++i) {
        for (int j = 0; j < col; ++j) {
            int num1, num2, sum = 0;
            for (int k = 0; k < arr1[0].size(); ++k) {
                num1 = arr1[i][k];
                num2 = arr2[k][j];
                sum = sum + (num1 * num2);
            }
            answer[i][j] = sum;
        }
    }
    
    return answer;
}

 

 

 

 

행렬의 곱셈에는 위처럼 단순히 O(N^3) 로 해결하는 것도 있지만,

O(N^2.807) 의 시간 복잡도를 갖는 슈트라센 알고리즘,

슈트라센 알고리즘과 동일한 시간 복잡도를 갖지만, 덧셈 연산 횟수를 더 줄인 위노그라드 알고리즘

슈트라센 보다 조금더 줄인 빅터 판의 알고리즘 (O(N^2.795))

O(N^2.376) 까지 줄인 Coppersmith–Winograd algorithm 등 여러가지 알고리즘이 존재한다.

 

 

 

아직 한참 미천한 실력이라 위의 다른 행렬 곱셈 알고리즘들이

PS 에 나온적이 있었는지는 잘 모르겠다.

(아마도 고수들의 시험에선 나왔을지도)

대학강의에서 슈트라센 까지는 봤었는데 다른 건 이번에 여러개 찾다보니 알게 됬다.