Programmers | Level 2 | 행렬의 곱셈

Programmers | Level 2 | 행렬의 곱셈

Problems

• 📘 Src: Programmers
• 🗂️ Cat: Matrix

Description

2차원 행렬 arr1과 arr2를 입력받아, arr1에 arr2를 곱한 결과를 반환하는 함수 solution을 완성해주세요.

Constraints

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

Examples

arr1	arr2	return
[[1, 4], [3, 2], [4, 1]]	[[3, 3], [3, 3]]	[[15, 15], [15, 15], [15, 15]]
[[2, 3, 2], [4, 2, 4], [3, 1, 4]]	[[5, 4, 3], [2, 4, 1], [3, 1, 1]]	[[19, 17, 9], [34, 28, 13], [26, 20, 11]]

Solutions

• ⏳ Time Complexity: O(n^3)
• 💾 Space Complexity: O(n^2)

import java.util.*;

class Solution {
    public int[][] solution(int[][] arr1, int[][] arr2) {
        int rowsA = arr1.length;  // arr1의 행 길이
        int colsA = arr1[0].length;  // arr1의 열 길이
        int colsB = arr2[0].length;  // arr2의 열 길이

        int[][] result = new int[rowsA][colsB];  // 결과 행렬 초기화

        // 행렬 곱셈 계산
        for (int i = 0; i < rowsA; i++) {
            for (int j = 0; j < colsB; j++) {
                for (int k = 0; k < colsA; k++) {
                    result[i][j] += arr1[i][k] * arr2[k][j];
                }
            }
        }

        return result;  // 결과 행렬 반환
    }
}

Approaches

이 문제는 행렬 곱셈을 수행하는 문제입니다. 행렬 곱셈은 두 행렬을 곱하여 새로운 행렬을 만드는 연산으로, 다음과 같은 규칙에 따라 이루어집니다:

• 행렬의 크기 조건:
  • 첫 번째 행렬의 열의 수는 두 번째 행렬의 행의 수와 같아야 합니다. 예를 들어, 첫 번째 행렬이 3행 2열이고 두 번째 행렬이 2행 4열이라면 두 행렬을 곱할 수 있습니다.
  • 결과 행렬의 크기는 첫 번째 행렬의 행 수와 두 번째 행렬의 열 수를 갖습니다. 예를 들어, 첫 번째 행렬이 3행 2열이고 두 번째 행렬이 2행 4열이면, 결과 행렬은 3행 4열이 됩니다.
• 행렬 곱셈 연산:
  • 결과 행렬의 (i, j) 원소는 첫 번째 행렬의 i번째 행과 두 번째 행렬의 j번째 열의 원소들의 곱의 합입니다.
  • 이를 식으로 표현하면 result[i][j] = Σ (arr1[i][k] * arr2[k][j]) 입니다. 여기서 k는 첫 번째 행렬의 열 또는 두 번째 행렬의 행의 인덱스를 의미합니다.

문제를 해결하기 위해 다음과 같은 접근 방식을 사용합니다:

• 행렬 초기화:
  • 첫 번째 행렬의 행 수와 두 번째 행렬의 열 수에 따라 결과 행렬 result를 초기화합니다.
  • 예를 들어, 첫 번째 행렬이 3행 2열이고 두 번째 행렬이 2행 4열이면 결과 행렬 result는 3행 4열이 됩니다.
• 행렬 곱셈 계산:
  • 첫 번째 행렬의 각 행을 순회합니다.
  • 두 번째 행렬의 각 열을 순회합니다.
  • 두 행렬의 해당 원소들의 곱을 계산하여 결과 행렬의 해당 위치에 저장합니다.
  • 예를 들어, 첫 번째 행렬의 i번째 행과 두 번째 행렬의 j번째 열을 곱하여 결과 행렬의 (i, j) 위치에 저장합니다.
• 결과 반환:
  • 계산된 결과 행렬을 반환합니다.

이 알고리즘의 시간 복잡도는 O(n^3)이며, 공간 복잡도는 O(n^2)입니다. 이는 주어진 문제를 효율적으로 해결하는 데 충분합니다.