[프로그래머스/C++] 행렬의 곱셈

미숙한 블로그 주인이 코딩테스트 문제를 풀어가는 과정을 담은 글입니다. 이 풀이가 효율적인 풀이가 아닐 수 있으며, 부정확한 정보가 많이 있을 수 있습니다. 보완해야할 점이 있다면 댓글로 남겨주세요!

 

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

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

행렬의 곱셈

문제

2차원 행렬 arr1과 arr2를 입력받아, arr1에 arr2를 곱한 결과를 반환하는 함수, solution을 완성해주세요.

제한사항

• 행렬 arr1, arr2의 행과 열의 길이는 2 이상 100 이하입니다.
• 행렬 arr1, arr2의 원소는 -10 이상 20 이하인 자연수입니다.
• 곱할 수 있는 배열만 주어집니다.

 

풀이

입출력 예시

 

풀이

파이썬이었다면 numpy를 이용해 한줄로 끝낼 수 있지만 C++은 그런 것 없었다.

 

행렬의 곱셈은 첫째 행렬의 열 수와 둘째 행렬의 행 수가 같을 때, 다음 방식으로 이루어진다.

$$A = \begin{pmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{pmatrix}, B = \begin{pmatrix} b_{11} & b_{12} \\ b_{21} & b_{22} \end{pmatrix} $$

$$ AB = \begin{pmatrix} a_{11}b_{11}+a_{12}b_{21} & a_{11}b_{12}+a_{12}b_{22} \\ a_{21}b_{11}+a_{22}b_{21} & a_{21}b_{12}+a_{22}b_{22} \end{pmatrix} $$

곱셈의 결과는 [첫째 행렬의 행] x [둘째 행렬의 열] 크기의 행렬이 만들어진다.

#include <string>
#include <vector>

using namespace std;

vector<vector<int>> matrixmulti(vector<vector<int>> arr1, vector<vector<int>> arr2) {
    // 첫째 행렬의 행 x 둘째 행렬의 열 크기로 초기화
    vector<vector<int>> answer(arr1.size(), vector<int>(arr2[0].size(), 0));
    
    return answer;
}

위의 행렬 곱셈식을 다시보자. 자세히 보면, AB[i][j] = A[i][0] * B[0][j] + A[i][1] * B[1][j] 이 된다는 것이 보인다. 이를 조금 바꾸면 AB[i][j] += A[i][k]*B[k][j] (k ≤ B의 행 수(또는 A의 열 수)) 가 됨을 알 수 있다.

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++) {
            answer[i][j] += arr1[i][k]*arr2[k][j];
        }
    }
}

전체 코드

#include <string>
#include <vector>

using namespace std;

vector<vector<int>> solution(vector<vector<int>> arr1, vector<vector<int>> arr2) {
    vector<vector<int>> answer(arr1.size(), vector<int>(arr2[0].size(), 0));

    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++) {
                answer[i][j] += arr1[i][k]*arr2[k][j];
            }
        }
    }

    return answer;
}

결과