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

문제

https://programmers.co.kr/learn/courses/30/lessons/12949?language=java 

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

 

풀이

행렬의 곱셈

두 행렬 A의 열의 개수와 행렬 B의 행의 개수가 같을 때 두 행렬을 곱할 수 있으며, 행렬A의 i행의 각 성분과 행렬 B의 j열의 각 성분을 순서대로 곱하여 더한 것을 새로운 곱셈 결과 행렬 C의 (i, j)성분으로 한다. 이때 행렬 C의 크기는 (행렬 A의 행의 개수 x 행렬 B의 열의 개수)이다.

(3 x 2) * (2 x 2) = (3 x 2)
- 행렬A의 열의 개수(2)와 행렬B의 행의 개수(2)가 같기 때문에 곱셈이 가능하다.

(3 x 2) * (2 x 2) = (3 x 2)
- 곱셈 결과 행렬 C의 행은 A의 행의 개수이고, 열은 B의 열의 개수 이다.

 

문제에서 준 테스트케이스의 이차원 배열을 행렬로 나타내면 아래와 같다.
answer행렬의 i행 j열 값은 arr1행렬 i행의 각 성분과 arr2행렬 j열의 각 성분을 순서대로 곱하여 더한 것이다.

answer[0][0] = arr1[0][0] * arr2[0][0] + arr1[0][1] * arr2[1][0]
15 = (1 * 3) + (4 * 3)

 

answer[0][1] = arr1[0][0] * arr2[0][1] + arr1[0][1] * arr2[1][1]
15 = (1 * 3) + (4 * 3)

 

위의 곱셈 공식을 적용한 결과 행렬의 각 칸의 값을 구해보자. 계산과정에서 arr1행렬은 행은 고정된 채로 열만 이동하고, arr2행렬은 열이 고정된 채로 행만 이동하는 것을 볼 수 있다. 또한, 각 칸에 대해 행렬 곱을 수행할 때 왼쪽 행렬은 (하나의 행에서)첫번째 열부터 끝 열까지, 오른쪽 행렬은 (하나의 열에서)첫번째 행부터 끝 행까지 값을 모두 계산에 사용하고 있다. (0~마지막 값)

answer[0][0] = arr1[0][0] * arr2[0][0] + arr1[0][1] * arr2[1][0]
arr1행렬은 행은 0으로 고정, 열만 0~1까지 이동함
arr2행렬은 열은 0으로 고정, 행만 0~1까지 이동함

answer[0][1] = arr1[0][0] * arr2[0][1] + arr1[0][1] * arr2[1][1]
arr1행렬은 행은 0으로 고정, 열만 0~1까지 이동함
arr2행렬은 열은 1로 고정, 행만 0~1까지 이동함

answer[1][0] = arr1[1][0] * arr2[0][0] + arr1[1][1] * arr2[1][0]
arr1행렬은 행은 1로 고정, 열만 0~1까지 이동함
arr2행렬은 열은 0으로 고정, 행만 0~1까지 이동함

answer[1][1] = arr1[1][0] * arr2[0][1] + arr1[1][1] * arr2[1][1]
arr1행렬은 행은 1로 고정, 열만 0~1까지 이동함
arr2행렬은 열은 1로 고정, 행만 0~1까지 이동함

 

여기서 각 연산에서 변경되는 값들을 증감 변수로 for문을 만든다.

• answer 행렬의 행 인덱스 i
• answer 행렬의 열 인덱스 j
• arr1 행렬의 행과 arr2 행렬의 열 인덱스 k

for (int i = 0; i < answer.length; i++) {
    for (int j = 0; j < answer[i].length; j++) {
        for (int k = 0; k < arr1[i].length; k++) {
            answer[i][j] += arr1[i][k] * arr2[k][j];
        }
    }
}

 

코드

class Solution {
    public int[][] solution(int[][] arr1, int[][] arr2) {
        int[][] answer = new int[arr1.length][arr2[0].length];
        
        // 결과 행렬 행
        for (int i = 0; i < answer.length; i++) {
            // 결과 행렬 열
            for (int j = 0; j < answer[i].length; j++) {
                // arr1의 열, arr2의 행 순회
                for (int k = 0; k < arr1[i].length; k++) {
                    answer[i][j] += arr1[i][k] * arr2[k][j];
                }
            }
        }

        return answer;
    }
}