회사 코딩 테스트 준비하면서 행렬 곱셈이 유명한 문제라고 해서 처음 접했다. 그때는 행렬이 뭔지도 몰라서 완전 멍했다... 진짜 부끄럽지만, 감도 안 왔던 때가 있었네. 그래도 이 문제 풀면서 행렬 곱셈이 뭔지 제대로 알게 돼서 다행이다. 행렬 곱셈이란? 행렬은 2차원 배열이라고 생각하면 된다. 행렬 곱셈은 두 개의 2차원 배열을 특정 규칙으로 곱하는 거다. 예를 들어, arr1이 m×n 크기이고 arr2가 n×p 크기라면, 결과 행렬은 m×p 크기가 된다. 핵심은 arr1의 i번째 행과 arr2의 j번째 열을 요소별로 곱해서 더한 값이 결과 행렬의 [i][j]에 들어간다는 점이다. 수학적으로 좀 생소할 수 있지만, 규칙만 알면 곱하고 더하는 거라 익숙해지면 괜찮다. 나의 풀이 처음엔 감이 안 와서 "배열 두 개를 그냥 곱하면 되나?" 이렇게 막연하게 접근했다. 근데 행렬 곱셈은 단순히 숫자 곱하는 게 아니라 특정 규칙이 필요하다는 걸 알게 됐다. 무작정 for 루프를 돌려봤는데, arr1의 행 수와 arr2의 열 수를 제대로 안 맞춰서 ArrayIndexOutOfBoundsException이 터졌다...ㅎ 암튼 구글링 좀 하고 행렬 곱셈 공식을 다시 보니까 감이 왔다. 생각보다 간단했다. arr1의 i번째 행이랑 arr2의 j번째 열을 곱해서 answer[i][j]에 더해주는 거였다. ↓↓ 나의 코드 ↓↓

class Solution {
    public int[][] solution(int[][] arr1, int[][] arr2) {
        
        int rows1 = arr1.length;
        int cols1 = arr1[0].length;
        int cols2 = arr2[0].length;
        // int rows2 = arr2.length;
        
        int[][] answer = new int[rows1][cols2];
        
        for(int i = 0; i < rows1; i++){
            for(int j = 0; j < cols2; j++){
                for(int k = 0; k < cols1; k++){
                    answer[i][j] += arr1[i][k] * arr2[k][j];
                }
            }
        }
        return answer;
    }
}

이 코드의 핵심은 세 개의 for 루프다. i는 arr1의 행, j는 arr2의 열, k는 arr1의 열이자 arr2의 행을 돌면서 곱셈을 처리한다. 처음엔 k 루프를 어디에 넣어야 할지 몰라서 i, j 바깥에 넣었다가 결과가 엉망이었다... 지금 보면 기본적인 구현인데, 그때는 왜 그렇게 복잡하게 생각했는지 모르겠다. 돌아보며.. 코드를 보면, 처음엔 행렬 크기 체크를 너무 꼼꼼히 하려고 arr2의 행 수까지 변수로 뽑았다. 근데 문제에서 곱할 수 있는 배열만 준다고 했으니 그건 필요 없었다. 그래서 주석으로 int rows2 = arr2.length;를 남겨뒀다. 그때 삽질한 걸 잊지 않으려고... 이 문제는 수학/구현 카테고리에 속하는데, 시간 복잡도가 O(n³)이라 좀 높다. 검색해보니 스트라센 알고리즘 같은 최적화 방법이 있다던데,, 근데 당시엔 "일단 풀자"만 생각해서 최적화는 전혀 고려 안 했다. 나중에 시간 되면 스트라센 알고리즘 공부해봐야겠다. 수학적 기반이 약한 내 단점을 또 마주해서 좀 부끄러웠다. 그래도 이번에 행렬 곱셈을 제대로 알게 돼서 다행이다. 처음에 너무 겁먹고 복잡하게 생각해서 시간 낭비한 게 아쉽다. 이런 수학/구현 문제는 공식을 외우고, 기본 문제를 많이 풀어보는 게 답인 거 같다. 풀이 팁 요약 - 행렬 크기부터 파악 : 결과 행렬의 크기는 arr1의 행 수 × arr2의 열 수다. 이걸 먼저 정하면 헷갈릴 일이 적다. - 공식 기억 : [i][j] 값은 arr1의 i번째 행과 arr2의 j번째 열을 곱해서 더한 거다. 이 공식을 외워두자. - 루프 순서 조심 : i, j, k 루프 순서를 잘못 잡으면 엉뚱한 값을 곱한다. k는 항상 가장 안쪽에 넣어야 한다. - 디버깅 팁 : 2×2 같은 작은 행렬로 손으로 계산해보면서 코드랑 맞춰보면 실수가 줄어든다.