[Programmers] Lv2. 행렬의 곱셈 | C++

🔗문제 보러가기

프로그래머스

 

👨‍💻풀이 과정

 

행렬 A와 행렬 B가 있다고 할 때, 다음과 같이 곱셈을 진행합니다.

// 행렬 A         // 행렬 B
2 3 2                5 4 3
4 2 4       X        2 4 1
3 1 4                3 1 1
------------------------------------------------------------------------------

/* A의 i번 행과 B의 j번 열 원소들을 각각 곱하여 합하기 */
(2 x 5) + (3 x 2) + (2 x 3) = 22    // A의 0행 x B의 0열
(2 x 4) + (3 x 4) + (2 x 1) = 22    // A의 0행 x B의 1열
(2 x 3) + (3 x 1) + (2 x 1) = 11    // A의 0행 x B의 2열

-> [22, 22, 11]

(4 x 5) + (2 x 2) + (4 x 3) = 36    // A의 1행 x B의 0열
(4 x 4) + (2 x 4) + (4 x 1) = 28    // A의 1행 x B의 1열
(4 x 3) + (2 x 1) + (4 x 1) = 18    // A의 1행 x B의 2열

-> [36, 28, 18]

A의 마지막 행도 위와 같이 진행하면,
-> [29, 20, 14]


따라서, 곱셈 결과로 얻는 행렬은 다음과 같다.
22 22 11
36 28 18
29 20 14

 

그렇다면, 여기서 필요한 건 다음과 같은 함수들입니다.

• 벡터 A와 벡터 B의 내적을 계산해줄 DotProduct()

// 두 벡터의 길이는 같아야 함

[1, 2, 3]  // 벡터 A
[4, 5, 6]  // 벡터 B

내적 = (1 x 4) + (2 x 5) + (3 x 6)

• 행렬 arr2의 행과 열의 형태를 바꿔주는 TransposedMatrix()  -> 사실 ReShape()이 더 맞을 것 같긴 합니다.

// 행렬 B는 열 방향으로 읽으므로, 코드에서 벡터를 하나씩 꺼내와 내적 계산하기 쉽게 하기 위해
// 변환해주는 것입니다.

1 4           1 2 3
2 5     ->    4 5 6
3 6

 

위 내용들을 바탕으로 코드를 작성하면 됩니다.

 

 

✏️소스 코드 및 결과

#include <vector>
using namespace std;
using Matrix = vector<vector<int>>;

int DotProduct(const vector<int>& vec1, const vector<int>& vec2) {
    int sum = 0;
    for (int i = 0; i < vec1.size(); i++)
        sum += (vec1[i] * vec2[i]);
    return sum;
}

Matrix TransposedMatrix(const Matrix& originMatrix) {
    Matrix result;
    int originRow = originMatrix.size();
    int originCol = originMatrix[0].size();
    
    // 열 방향으로 읽기
    for (int c = 0; c < originCol; c++) {
        vector<int> row;

        for (int r = 0; r < originRow; r++)
            row.push_back(originMatrix[r][c]);
        result.push_back(row);
    }

    return result;
}

vector<vector<int>> solution(vector<vector<int>> arr1, vector<vector<int>> arr2) {
    Matrix answer;
    Matrix transposedArr2 = TransposedMatrix(arr2);

    for (int a1i = 0; a1i < arr1.size(); a1i++) {
        vector<int> row;

        for (int a2i = 0; a2i < transposedArr2.size(); a2i++) {
            int sum = DotProduct(arr1[a1i], transposedArr2[a2i]);
            row.push_back(sum);
        }

        answer.push_back(row);
    }

    return answer;
}