[Programmers](Level2) 행렬의 곱셈

문제명: 행렬의 곱셈

문제설명

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

문제풀이

이 문제를 이해하는데 시간이 꽤 걸렸다. 테스트 케이스를 암만 봐도 어떻게 값이 떨어지는 지 이해가 안되더라
알고보니 선형대수에 대한 이해가 필요한 부분이었다.(수포자는 웁니다ㅠㅠ)

행렬의 곱셈을 풀기 위해선 아래에 대한 설명을 이해할 필요가 있다.

행렬의 곱은 첫째 행렬(A)의 열 개수와 둘째 행렬(B)의 행 개수가 동일해야한다. 

즉, A행렬이 (mk)행렬이고, B 행렬이 (kn)행렬이라고 할 때 
(A행렬의 열의 개수 k) = (B의 행의 개수 k)가 같아야 성립이 된다.

그럴때 AB행렬의 곱은 m*n행렬이다.

위의 사진과 같을 때 아래와 같이 행열의 곱셈을 반복해서 더 해준다.

곱셈의 결과 새롭게 만들어진 행렬은 행렬곱(matrix product)이라 하며, 첫째 행렬의 행 개수와 둘째 행렬의 열 개수를 가진다.

행렬곱의 값은 AB[i][j] += A[i][n] * B[n][j] 형태의 알고리즘을 통해 풀 수 있다.

그럼 한 번 풀어보자!

function solution(arr1, arr2) {
  // 정답인 2차원 배열을 초기화할 때 첫째 행렬의 행의 갯수와, 둘째 행렬의 열의 갯수로 만들어준다.
  // 0으로 값을 채워줘야 덧셈이 가능하다 (0으로 안할 경우 NaN)
  let answer = Array.from(Array(arr1.length), () => new Array(arr2[0].length).fill(0));
  
  // 행의 길이만큼 반복
  for(let i = 0; i < arr1.length; i++) {
    // 열의 길이만큼 반복
    for(let j = 0; j < arr2[0].length; j++) {
      //  연산 횟수 (두개의 행렬 길이가 같은 값)
      // arr1[0].length || arr2.length
      for(let count = 0; count < arr1[0].length; count++) {
        answer[i][j] += arr1[i][count] * arr2[count][j]    
      }
    }
  }
  return answer
};

이 문제는 3개의 for문마다 반복 길이 설정이 중요한 요소였고, 행렬의 곱셈 이론을 이해하고 풀어야 하는 문제여서 좀 까다로웠던 문제였다.

끗.

Reference

• https://mathbang.net/562
• https://blog.naver.com/crud0626/222670123608
• https://blog.naver.com/dlrhkdgh3333/222595434848