[PCCP] Lv2: 행렬의 곱셈(12949) 해설

문제

- 문제 링크: 행렬의 곱셈

 

해설

- 자료구조: 

- 시간복잡도: 

 

(풀이과정)

1) 

2) 

3) 

4) 

 

코드

(C언어) 

 

(C++) 

solution 1)

- N: 행 혹은 열의 길이

- r1는 arr1의 행의 수, c1는 arr1의 열의 수

- r2는 arr2의 행의 수, c2는 arr2의 열의 수

- 총 r1 * c1 * c2만큼 연산

- 최종 시간 복잡도: O(N^3)

#include <string>
#include <vector>

using namespace std;

vector<vector<int>> solution(vector<vector<int>> arr1, vector<vector<int>> arr2) {
    // 최종 행렬 곱의 결과를 저장할 벡터 선언
    vector<vector<int>> answer;
    
    // arr1과 arr2의 행렬 곱을 수행했을 때 최종 행렬의 크기만큼 공간 할당
    answer.assign(arr1.size(), vector<int>(arr2[1].size(), 0));

    // arr1의 각 행과 arr2의 각 열에 대한 반복문 수행
    for (int i = 0; i < arr1.size(); ++i) {
        for(int j = 0; j < arr2[1].size(); ++j) {
            for (int k = 0; arr2.size(); ++k) {
                answer[i][j] += arr1[i][k] * arr2[k][j]; // 두 행렬의 곱 수행
            }
        }
    }

    return answer;
}

solution 2)

#include <string>
#include <vector>

using namespace std;

vector<vector<int>> solution(vector<vector<int>> arr1, vector<vector<int>> arr2) {
    vector<vector<int>> answer;
    
    for (int i = 0; i < arr1.size(); i++)
    {
        vector<int> new_arr;
        answer.push_back(new_arr);
        for (int j = 0; j < arr2[0].size(); j++)
        {
            int tmp = 0;
            for (int k = 0; k < arr1[0].size(); k++)
            {
                tmp += arr1[i][k] * arr2[k][j];
            }
            answer[i].push_back(tmp);
        }
    }
    return answer;
}

solution 3)

#include <string>
#include <vector>

using namespace std;

vector<vector<int>> solution(vector<vector<int>> arr1, vector<vector<int>> arr2) {
    vector<vector<int>> answer;
    
    for (size_t i = 0; i < arr1.size(); ++i){
        vector<int> tmp;
        for (size_t j = 0; j < arr2[0].size(); ++j){
            int res = 0;
            for (size_t k = 0; k < arr1[0].size(); ++k){
                res += arr1[i][k]*arr2[k][j];
            }
            tmp.push_back(res);
        }
        answer.push_back(tmp);
    }
    
    return answer;
}

 

(C#) 

 

(Java) 

solution1)

- N: 행과 열의 길이

- arr1의 행을 r1, 열을 c1이라하고 arr2의 행을 r2, 열을 c2라고 했을 때 r1*c1*c2만큼 연산

- r1, c1, r2,c2 모두 N으로 볼 수 있으므로 최종 시간 복잡도: O(N^3)

class Solution {
    public int[][] solution(int[][] arr1, int[][] arr2) {
		// 행렬 arr1과 arr2의 행과 열의 수
        int r1 = arr1.length;
        int c1 = arr1[0].length;
        int r2 = arr2.length;
        int c2 = arr2[0].length;
        
        // 결과를 저장할 2차원 배열 초기화
        int[][] answer = new int[r1][c2];
        
        // 첫 번쨰 행렬 arr1의 각 행과 두 번째 행렬 arr2의 각 열에 대해
        for (int i = 0; i < r1; ++i) {
            for (int j = 0; j < c2; ++j) {
                // 두 행렬의 데이터를 곱해 결과 리스트에 더함
                for (int k = 0; k < c1; ++k) {
                    answer[i][j] += arr1[i][k] * arr2[k][j];
                }
            }
        }
    return answer;
    }
}

solution2) 

class Solution {
      public int[][] solution(int[][] arr1, int[][] arr2) {
          int[][] answer = new int[arr1.length][arr2[0].length];

          for(int i = 0 ; i < arr1.length ; ++i){
              for(int j = 0 ; j < arr2[0].length ; ++j){
                  for(int k = 0 ; k < arr1[0].length ; ++k) {
                      answer[i][j] += arr1[i][k] * arr2[k][j];
                  }
              }
          }

          return answer;
      }
  }

solution3) 

 

 

(Python) 

solution1) 

- N: 행 혹은 열의 길이. 행과 열의 길이는 동일

- r1, c1: arr1의 행과 열의 수

- r2, c2: arr2의 행과 열의 수

- 총 연산 수는 r1*c1*c2이므로 최종 시간 복잡도: O(N^3)

def solution(arr1, arr2):
    # 행렬 arr1과 arr2의 행과 열의 수
    r1, c1 = len(arr1), len(arr1[0])
    r2, c2 = len(arr2), len(arr2[0])
    
    # 결과를 저장할 2차원 리스트 초기화
    ret = [[0] * c2 for _ in range(r1)]
    
    # 첫 번째 행렬 arr1의 각 행과 두 번쨰 행렬 arr2의 각 열에 대해
    for i in range(r1):
        for j in range(c2):
            # 두 행렬의 데이터를 곱해 결과 리스트에 더해줌
            for k in range(c1):
                ret[i][j] += arr1[i][k] * arr2[k][j]
    return ret

solution2)

def solution(arr1, arr2):
    answer = []
    r1, c1 = len(arr1), len(arr1[0])
    r2, c2 = len(arr2), len(arr2[0])
    
    result = [[0 for _ in range(c2)] for _ in range(r1)]
    for i in range(r1):
        for j in range(c2):
            for k in range(c1):
                result[i][j] += arr1[i][k] * arr2[k][j]
    return result

solution3) 

 

 

(JavaScript) 

solution1)

- N: 행 혹은 열의 길이. 행과 열의 길이는 동일

- r1, c1: arr1의 행과 열의 수

- r2, c2: arr2의 행과 열의 수

- 총 연산 수는 r1*c1*c2이므로 최종 시간 복잡도: O(N^3)

function solution(arr1, arr2) {
    // 행렬 arr1과 arr2의 행과 열의 수
    const r1 = arr1.length;
    const c1 = arr1[0].length;
    const r2 = arr2.length;
    const c2 = arr2[0].length;
    
    // 결과를 저장할 2차원 배열 초기화
    const ret = [];
    for (let i = 0; i < r1; ++i) {
        ret.push(new Array(c2).fill(0));
    }
    
    // 첫 번째 행렬 arr1의 각 행과 두 번째 행렬 arr2의 각 열에 대해
    for (let i = 0; i < r1; ++i) {
        for (let j = 0; j < c2; ++j) {
            // 두 행렬의 데이터를 곱해 결과 배열에 더해줌
            for (let k = 0; k < c1; ++k) {
                ret[i][j] += arr1[i][k] * arr2[k][j];
            }
        }
    }
    
    return ret;
}

solution2)

function solution(arr1, arr2) {
    return arr1.map((row) => arr2[0].map((x,y) => row.reduce((a,b,c) => a + b * arr2[c][y], 0)));
}