프로그래머스 [연습문제 / 행렬의 곱셈](C++) -yes6686- 티스토리

프로그래머스 문제 풀이: 12949 행렬의 곱셈

---

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/12949

문제 설명:

2차원 행렬 arr1과 arr2를 입력받아 arr1에 arr2를 곱한 결과를 반환하는 문제입니다. 행렬의 행과 열의 길이는 2 이상 100 이하이며, 원소는 -10 이상 20 이하의 정수입니다. 행렬 곱셈의 기본 원리를 이해하고 3중 반복문을 활용하여 구현해야 합니다.

---

문제 해결 코드

#include <string>
#include <vector>
using namespace std;

vector<vector<int>> solution(vector<vector<int>> arr1, vector<vector<int>> arr2) {
    // 결과 행렬의 크기: arr1의 행 × arr2의 열
    int rows = arr1.size();        // 첫 번째 행렬의 행 개수
    int cols = arr2[0].size();     // 두 번째 행렬의 열 개수
    int common = arr2.size();      // 공통 차원 (arr1의 열 = arr2의 행)
    
    // 결과 행렬 초기화
    vector<vector<int>> answer(rows, vector<int>(cols, 0));
    
    // 행렬 곱셈 수행
    for(int i = 0; i < rows; i++) {
        for(int j = 0; j < cols; j++) {
            // answer[i][j] = arr1의 i번째 행과 arr2의 j번째 열의 내적
            for(int k = 0; k < common; k++) {
                answer[i][j] += arr1[i][k] * arr2[k][j];
            }
        }
    }
    
    return answer;
}

---

코드 설명

• 핵심 알고리즘: 행렬 곱셈의 정의를 직접 구현한 방식입니다. A × B 행렬 곱셈에서 결과 행렬 C[i][j]는 A의 i번째 행과 B의 j번째 열의 내적(각 원소를 곱한 후 합산)으로 계산됩니다. m×n 크기의 행렬과 n×p 크기의 행렬을 곱하면 m×p 크기의 결과 행렬이 생성됩니다.
• 구현 세부사항:
  • 결과 행렬의 크기를 arr1의 행 개수와 arr2의 열 개수로 결정하고 0으로 초기화합니다.
  • 3중 반복문을 사용하여 결과 행렬의 각 위치 (i, j)에 대해 계산을 수행합니다.
  • 가장 안쪽 반복문에서 arr1[i][k]와 arr2[k][j]를 곱한 값들을 누적하여 answer[i][j]를 완성합니다.
  • 변수명을 rows, cols, common으로 명확하게 지정하여 가독성을 높였습니다.
• 시간/공간 복잡도: 시간 복잡도는 O(rows ⋅ cols ⋅ common)으로, 최악의 경우 O(100 ⋅ 100 ⋅ 100) = O(1,000,000) 연산이 필요하지만 충분히 효율적입니다. 공간 복잡도는 O(rows ⋅ cols)로 결과 행렬을 저장하는 공간이 필요합니다.

---

실행 예시

입력:

arr1 = [[1, 2], [3, 4]]
arr2 = [[5, 6], [7, 8]]

실행 과정:

• 결과 행렬 크기: 2×2
• answer[0][0] = 1×5 + 2×7 = 5 + 14 = 19
• answer[0][1] = 1×6 + 2×8 = 6 + 16 = 22
• answer[1][0] = 3×5 + 4×7 = 15 + 28 = 43
• answer[1][1] = 3×6 + 4×8 = 18 + 32 = 50

출력:

[[19, 22], [43, 50]]

---

결과

행렬 곱셈의 기본 원리를 3중 반복문으로 구현하여 모든 테스트 케이스를 통과했습니다. 행렬의 크기가 최대 100×100까지 주어지므로 O(n³) 복잡도로도 충분히 효율적으로 동작합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!