행렬 곱셈(백준 2740번, 수학/구현, NodeJS풀이)

https://www.acmicpc.net/problem/2740

 

 

문제 수준:

실버5

 

문제 요약:

행렬 A와 B가 주어졌을 때 행렬곱셈 값을 구하여라.

 

 

입출력 예 (입력 / 출력):

 

 

문제 풀이 전략:

행렬과 행렬의 곱셈을 어떻게 구하는지 몰라서 일단 아래 블로그와 영상을 참고했다.

수1에 나오는 내용이라고 한다. 지금 중등 수학 복습 중인데 조만간 따라잡아야겠다.

 

참고한 블로그:

https://blog.naver.com/cindyvelyn/222136360080

 

참고한 영상:

https://www.youtube.com/watch?v=JpSe38UHaos

 

 

일단 입력값이 조금 불친절하다.

행렬에 대한 메타데이터 형식이 실제데이터와 동일할 가능성이 있기 때문이다.

그래서 메타데이터의 문자열만 집어내서 이를 기준으로 파싱하는 것이 까다로웠다.

//2740 행렬 곱셈
let fs = require("fs");
let input = fs.readFileSync("input.txt").toString().trim().split("\n");

let tcs = []; // testCases

for (let i = 0; i < input.length; i++) {
  const [Y, X] = input[i].split(" ").map(Number);

  let j;
  const tempArr = [];

  for (j = i + 1; j <= i + Y; j++) { // 현재 '인덱스 + 1'부터 '인덱스 + Y'까지 반복
    const spl = input[j].split(" ");
    tempArr.push(spl); // I ~ I+7줄까지의 내용을 tempArr에 넣기
  }
  tempArr.push([Y, X]); // 마지막으로 행렬에 대한 정보 Y,X를 tempArr에 넣어준다.
  tcs.push(tempArr);// // 테스트케이스 배열에 넣어준다.
  i = j - 1;
}

/*
[
  [ [ '1', '2' ], [ '3', '4' ], [ '5', '6' ], [ 3, 2 ] ],
  [ [ '-1', '-2', '0' ], [ '0', '0', '3' ], [ 2, 3 ] ]
]
*/

 

 

 

필기 안 하고 암산으로 풀려고 했는데 생각보다 복잡해서

결국 노트에 두 행렬의 col, row가 어떤 순서로 계산되어서 어떤 위치에 들어가야하는지를 그려보았다.

대강 노트에 끄적였던걸 그림판으로 그려보면 아래와 같다.

 

 

 

행렬 곱이 성립하려면 한 객체는 N x M이고 다른 한 객체는 M x L이어야 한다. 즉 한 변 M과 같이 동일한 수여야 한다.

이를 코드로 구현하려면 삼중포문을 썼어야했다. N의 변화와 L의 변화와 M의 변화를 모두 담아야하기 때문이다.

구현 코드는 아래와 같다.

 

내 풀이:

let fs = require("fs");
let input = fs.readFileSync("input.txt").toString().trim().split("\n");

// 1. 입력값에서 행렬을 파싱하기
let tcs = [];

for (let i = 0; i < input.length; i++) {
  const [Y, X] = input[i].split(" ").map(Number);

  let j;
  const tempArr = [];

  for (j = i + 1; j <= i + Y; j++) {
    const spl = input[j].split(" ");
    tempArr.push(spl);
  }
  tempArr.push([Y, X]);
  tcs.push(tempArr); // 메타 데이터를 그냥 마지막에 한 번 넣어줬다.
  i = j - 1;
}

// 2. 파싱한 행렬 A, B를 서로 곱해주기
const [A, B] = tcs; // A와 B행렬

const [AY, AX] = A.pop(); // 마지막에 넣은 메타데이터를 pop해서 구조분해할당
const [BY, BX] = B.pop(); // 마지막에 넣은 메타데이터를 pop해서 구조분해할당

for (let i = 0; i < AY; i++) { // A객체의 Y방향으로 순회
  const AYrow = [];
  for (let j = 0; j < BX; j++) { // B객체의 X방향으로 순회
    let temp = 0;
    for (let k = 0; k < BY; k++) { // B객체의 Y방향으로 순회
      temp += +A[i][k] * +B[k][j];
    }
    AYrow.push(temp);
  }

  console.log(AYrow.join(" "));
}