프로그래머스 12949 - 행렬의 곱셈 (Lv.2)

출처: https://school.programmers.co.kr/learn/courses/30/lessons/12949

// 프로그래머스 12949 - 행렬의 곱셈 (Lv.2)
// https://school.programmers.co.kr/learn/courses/30/lessons/12949

// 문제 설명
// 2차원 행렬 arr1, arr2가 주어질 때 arr1 x arr2의 행렬 곱을 반환하라.
// 곱할 수 있는 짝(arr1 열 수 == arr2 행 수)만 입력으로 들어온다.

// 제약 조건
// 행렬의 행/열 길이는 2 이상 100 이하
// 원소는 -10 이상 20 이하

// Example
// Input : arr1 = [[1,4],[3,2],[4,1]], arr2 = [[3,3],[3,3]]
// Output: [[15,15],[15,15],[15,15]]

// 접근 — 정의대로 3중 루프, 순회 순서만 i-k-j
// 1) 결과는 r x c (r = arr1 행 수, c = arr2 열 수), 공유 차원 m = arr2 행 수.
//    answer[i][j] = sum(arr1[i][k] * arr2[k][j]) 를 그대로 계산한다.
// 2) 루프를 i-j-k 대신 i-k-j로 돌리면 안쪽 루프가 arr2[k][0..c-1]를
//    행 방향(연속 메모리)으로 읽어 캐시 적중률이 좋아진다.
// 3) 결과를 0으로 초기화해 두고 누적하면 별도 임시 변수가 필요 없다.
// 시간 O(r*m*c) — 최악 100^3 = 100만, 공간 O(r*c)

#include <vector>

using namespace std;

vector<vector<int>> solution(vector<vector<int>> arr1, vector<vector<int>> arr2) {
    int r = arr1.size(), c = arr2[0].size(), m = arr2.size();
    vector<vector<int>> answer(r, vector<int>(c, 0));

    for (int i = 0; i < r; i++)
        for (int k = 0; k < m; k++)          // i-k-j 순서: arr2를 행 방향으로 읽어 캐시 친화적
            for (int j = 0; j < c; j++)
                answer[i][j] += arr1[i][k] * arr2[k][j];
    return answer;
}

정리

• 결과 행렬의 크기부터 고정하고 시작한다. (r x m) x (m x c) = (r x c) — 행은 arr1에서, 열은 arr2에서 온다. 이 크기 계산이 흔들리면 인덱스 범위가 전부 꼬이므로 코드 첫 줄에서 r, c, m을 이름 붙여 박아두는 게 안전하다.
• 교과서식 i-j-k 순서는 안쪽 루프에서 arr2[k][j]의 k가 변해 열 방향(불연속 메모리)으로 점프한다. i-k-j로 바꾸면 안쪽 루프가 arr2[k][0..c-1]을 연속으로 읽어 캐시 라인을 그대로 태운다. 이 제약(100^3)에서는 체감 차이가 없지만, 행렬이 커지면 수 배 차이가 나는 표준 최적화다.
• i-k-j가 성립하려면 결과를 미리 0으로 초기화해 두고 누적해야 한다(vector<int>(c, 0)). j 루프가 완결되기 전에 다른 k가 같은 칸에 더해지기 때문이다.
• 원소 최대 20, 공유 차원 최대 100이면 한 칸의 최댓값은 20 x 20 x 100 = 40,000이라 int로 충분하다. 곱셈 문제를 만나면 누적값의 상한부터 계산해 자료형을 정하는 습관이 오버플로 사고를 막는다.
• 검증: 예제 [[1,4],[3,2],[4,1]] x [[3,3],[3,3]] → [[15,15],[15,15],[15,15]], [[2,3,2],[4,2,4],[3,1,4]] x [[5,4,3],[2,4,1],[3,1,1]] → [[22,22,11],[36,28,18],[29,20,14]] 통과(MSVC /std:c++17 컴파일·실행).