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

학교 다닐 때 이산수학 시간에 했던 행렬을 까먹은지 오래 되어서 기억이 안나서 어떻게 계산하는지 먼저 생각하는게 더 오래 걸렸다.

 

📔 문제

프로그래머스

 

• 문제 내용

2차원 행렬 arr1과 arr2를 입력받아, arr1에 arr2를 곱한 결과를 반환하는 함수 구하기

 

• 제한 조건

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

 

📖 문제 풀이

먼저 이 문제를 풀려면 행렬을 이해해야 한다.

 

나는 아래 칸 아카데미 수업을 듣고 해당 방식을 알고리즘으로 구현했다.

 

행렬 곱셈의 크기 (개념 이해하기) | 행렬 | Khan Academy

 

🔍 여기서 내가 했던 실수는 for문을 어떻게 만들지 감이 안와서 계속 이상한 변수를 넣어보았다는 것. 머리로 잘 상상이 되지 않는다면 그냥 System.out.println으로 찍어보는 걸 추천한다.

 

행렬의 구조를 이해했다면 예시 1번을 먼저 예시로 이해를 하겠다.

 

배열을 행렬로 변환 시키면 아래와 같은 구조가 된다.

 

그러면 먼저 곱을 구해야 한다. 그렇다면 순서는 어떻게 될까?

 

 

바로 이렇게 된다. 

 

이거를 배열 좌표에 맞게 그려본다면 아래와 같이 된다.

 

 

1. arr1[0][0] * arr2[0][0] = 1 * 3 = 3
2. arr1[0][1] * arr2[1][0] = 4 * 3 = 3

식으로 해서 answer[0][0] = 3 + 12 = 15로 채우게 된다.

 

그래서 총 순서를 한번 확인해 본다면

 

 

이런식으로 채워나가야 한다는 소리다.

 

그러면 이걸 for문으로 하나씩 채울 수 있다는 것이다.

 

이 for문을 만드는게 제일 시간이 오래걸렸는데 하나씩 찍어보면서 해보면 답이 나온다. 

 

오타 있습니다. 아래 공식을 내부에 넣는 겁니다!

 

먼저 answer[ j ][ 0 ] += arr1[ j ][0] * arr2[0][0] 으로 넣어보는 거다.

 

그러면 위 for문대로 돌리면 저렇게 잘 들어간다. 그런데 저게 정답이 될 순 없다. 그러면 남은 수를 더해줘야 한다.

 

 

첫번 째 줄이 완성 되었다. 그러면 나머지도 똑같이 돌려서 두번 째 줄을 맞추면 된다.

 

 

그렇다면 코드 완성이다!

 

✅ 소스 코드

class Solution {
    public int[][] solution(int[][] arr1, int[][] arr2) {
        
        int[][] answer = new int[arr1.length][arr2[0].length];
        int cnt = 0;
        
        // arr2[0].length을 해야 [3, 3] 의 x 개수를 맞출 수 있습니다.
        for(int x = 0; x < arr2[0].length; x++){
            for(int i = 0; i < arr2.length; i++)  {
               for(int j = 0; j < arr1.length; j++) {
                   answer[j][x] += arr1[j][i] * arr2[i][x];
               }   
            }
        }
        
        return answer;
    }
}

 

 

이틀 동안 1시간씩 시간을 투자해서 했는데 역시 먼저 종이에 그려보고, 구조를 알 것 같다면 코드 짜보고 예상대로 안나오면 찍어보는 수 밖에 없는 것 같다. 그리고 반례를 찾는 것도 매우 중요하기에 질문하기에서 반례를 찾아보자. 

 

나는 도움 받았던 반례가 

arr1 = [[1, 2], [2, 1]], arr2 = [[1, 1, 1, 1], [2, 2, 2, 2]], answer = [[5, 5, 5, 5], [4, 4, 4, 4]] 였다!