[C++] Programmers Lv. 2 "행렬의 곱셈"

🔵 문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/12949

프로그래머스

 

🔵 풀이

배열의 최대 행, 열의 길이가 100이기 때문에 시간 복잡도 걱정 없이 구현할 수 있다. 

구현 방법도 간단한데, 행렬의 곱셈을 코드로 그대로 옮겨적으면 된다.

 

💡행렬의 곱셈

예시 행렬이 위와 같다고 가정하자.

 

 

제일 첫 행렬을 A, 다음 행렬을 B라고 했을 때, A의 열의 개수와 B의 행의 개수가 같아야 행렬의 곱셈을 할 수 있다.

문제에선 곱할 수 있는 행렬만 주어 예외 처리를 할 필요가 없다.

 

행렬 곱셈의 결과는 위와 같다.

결과 행렬의 크기는 "A의 행의 개수 X B의 열의 개수", 즉 2 X 3이 된다.

 

🔵코드

#include <string>
#include <vector>

using namespace std;

vector<vector<int>> solution(vector<vector<int>> arr1, vector<vector<int>> arr2) {
    vector<vector<int>> answer;
    
    // 최종 행렬 크기 설정
    answer.resize(arr1.size(), vector<int>(arr2[0].size()));

    for (int i = 0; i < arr1.size(); i++)            // 결과 행렬의 행
        for (int j = 0; j < arr2[0].size(); j++)     // 결과 행렬의 열
            for (int k = 0; k < arr2.size(); k++)    // 곱셈합 요소들, k < arr1[0].size()도 결과가 같다
                answer[i][j] += arr1[i][k] * arr2[k][j];

    return answer;
}

 

🔵 시간 복잡도

for문 3개 중첩으로, 각 size의 최대 개수는 N이므로 최종 시간 복잡도는 O(N^3)이다.