행렬의 곱셈

내 생각

행렬의 곱셈이 가물가물 했다. 어렸을 때 배웠던 걸로 기억하는데, 여하튼 행렬의 곱셈을 살펴보기로 하였다.

 

출처 : https://mathbang.net/562#gsc.tab=0

그림을 보니 예전 기억이 다시 돌아왔는데, 행렬의 곱셈에서는 특정한 조건이 있다. 바로 곱하려는 matrix1 의 행의 갯수와 matrix2 의 열의 갯수가 같아야 한다는 점이다. 위에 그림을 참고하면 무슨말인지 바로 이해할 수 있을것이다.

 

다행이도 프로그래머스 문제 조건에는 곱할 수 있는 행렬들만 인자로 주어진다고 한다. 그러니 이 부분에 대해서는 딱히 신경쓰지 않아도 될 듯 하다. 다만, 추후에 랜덤한 행렬이 오는 경우라면 조건을 걸어주어야 할 듯 싶다.

 

저번 문제의 실수를 하지 않기 위해, 시간 복잡도를 먼저 따져보았다. 각 행렬의 행과 열의 최대값은 100! 따라서 n = 100 이니 여유롭다고 할 수 있겠다. 어째서 여유롭게 주었는지에 대해서는 문제를 풀이하다보면 알 수 있다.

 

결론적으로 문제 그대로 행렬의 곱셈을 구현하면 되는 것이다. 풀어보자

 

내가 푼 풀이

행렬은 언제나 익숙치 않다. 많이 다루어 보지 않았기 때문이라 생각한다. 이번 기회에 다시 다루어보자

 

우선 어떻게 반복해야 할 것인지를 정해보자. 행렬을 쉽게 각각 mat1, mat2 라고 하고 mat1 * mat2 라고 하겠다.

 

• mat1 의 열(column) 만큼 반복해주어야 한다. (i)
• mat2 의 행(row) 만큼 반복해주어야 한다. (j)
• 각각의 원소를 곱해 더할 때, 반복횟수는 mat1의 행이거나, mat2의 열이면 된다.(k)

세상에... 3중이다. n^3 이지만 다행이도 n = 100 이니 1억을 넘기지 않는다. (보통 1억을 기준으로 한다)

 

이제 3번을 반복해야함을 알았고, 가장 윗단계부터 무엇이 만들어져야되는지 상상하면서 코드를 작성하자.

function solution(arr1, arr2) {
    const matrix = [];
    
    // 가장 상위 반복인 arr1 의 열만큼의 반복
    for(let i = 0; i < arr1.length; i++){
    // 반복할 때마다 rows 행렬을 만든다.
        const rows = [];
        // arr2 의 행만큼 반복을 하게 된다.
        for(let j = 0; j < arr2[0].length; j++){
            // 각각의 합을 구할것임
            let sum = 0;
            // 원소마다 곱을 해줄 것이다.
            for(let k = 0; k < arr2.length; k++){
                sum += arr1[i][k] * arr2[k][j];
            }
          // rows 에다가 각각의 원소들을 넣어준다
            rows.push(sum)
        }
        // matrix 에 rows 를 넣어준다.
        matrix.push(rows);
    }
    
    return matrix
    
}

절차적인 풀이 방법이고, 고차함수를 사용할 수 있었지만 이해하기는 이게 더 편하긴 한것 같다. 여하튼 제출을 해보면 정답으로 나오게 된다. 

---

간단한거 같으면서도 행렬을 햇갈려하는 나에게 있어서는 꽤나 생각이 들어가는 문제였다. 반성해야겠다... 나중에 더 어려운건 어떻게 풀려고..

 

참고로 배열의 고차함수를 통해 풀면 다음과 같다.

unction productMatrix(A, B) {
    return A.map(function(row) {
        return row.map(function(_, i) {
            return row.reduce(function(sum, cell, j) {
                return sum + cell * B[j][i];
            }, 0);
        });
    });
}