[200904] 행렬의 곱셈 - 연습문제(level2)

1. 문제 이해

- 2차원 행렬 arr1과 arr2의 곱한 결과를 반환

(단, 곱할 수 있는 형태로 주어짐 : (axb) X (bxc) )

 

 

2. 전략

1) 필요한 변수 정의

- width = arr1.length = answer의 행 수

- height = arr2[0].length = answer의 열 수

- num = arr1[0].length = arr2.length = arr1과 arr2의 교차 행/열 수

 

2) 행렬 곱셈 : O(n3)

- arr1의 행과 arr2의 열을 선택(중첩 for문 → i, j) 

- answer[i][j] = arr1[i][0]*arr2[0][j] + arr[i][1]*arr2[1][j] + . . .  + arr[i][num]*arr[num][j]  (for문 이용)

 

 

3. 참고 사항

1) Divide and Conquer 알고리즘 - O(n3)

- 행렬의 영역을 나눠서 계산한다. 

(단, 이 경우에는 각 행렬이 모두 n X n 행렬이여야 됨)

- 각 영역에 대해 재귀연산 진행

 

 

4. 코드

class Solution {
    public int[][] solution(int[][] arr1, int[][] arr2) {
        int width = arr1.length; int height = arr2[0].length; int num = arr2.length;
        int[][] answer = new int[width][height];
        for(int i = 0; i < width; i++){
            for(int j = 0; j < height; j++){
                int temp = 0;
                for(int k = 0; k < num; k++){
                    temp += arr1[i][k] * arr2[k][j];
                }
                answer[i][j] = temp;
            }
        }
        return answer;
    }
}