코드워즈 - Square Matrix Multiplication (01/21) (java)

1. 문제

www.codewars.com/kata/5263a84ffcadb968b6000513

Codewars: Achieve mastery through challenge

문제 설명

Write a function that accepts two square (NxN) matrices (two dimensional arrays), and returns the product of the two. Only square matrices will be given.

How to multiply two square matrices:

We are given two matrices, A and B, of size 2x2 (note: tests are not limited to 2x2). Matrix C, the solution, will be equal to the product of A and B. To fill in cell [0][0] of matrix C, you need to compute: A[0][0] * B[0][0] + A[0][1] * B[1][0].

More general: To fill in cell [n][m] of matrix C, you need to first multiply the elements in the nth row of matrix A by the elements in the mth column of matrix B, then take the sum of all those products. This will give you the value for cell [m][n] in matrix C.

입출력 예

a = {{1,2} {3,2}}

b = {{3,2},{1,1}}

result = {{5,4}{11,8}}

---

2. 어떻게 풀까?

• n x n 행렬곱이기 때문에 결과도 n x n 행렬이 나온다. 직관적으로 일단 이중 for문이 필요하긴 할 것.
• result[0][0] = (a[0][0] * b[0][0]) + (a[0][1] * b[1][0]) + (a[0][2] * b[2][0]) + ... + (a[0][n] * b[n][0])
• result[0][1] = (a[0][0] * b[0][1]) + (a[0][1] * b[1][1]) + (a[0][2] * b[2][1]) + ... + (a[0][n] * b[n][1])
• result[0][2] = (a[0][0] * b[0][2]) + (a[0][1] * b[1][2]) + (a[0][2] * b[2][2]) + ... + (a[0][n] * b[n][2])
• result[0][k] = (a[0][0] * b[0][k]) + (a[0][k] * b[1][k]) + (a[0][2] * b[2][k]) + ... + (a[0][n] * b[n][k])

 

• result[1][0] = (a[1][0] * b[0][0]) + (a[1][1] * b[1][0]) + (a[1][2] * b[2][0]) + ... + (a[1][n] * b[n][0])
• result[2][0] = (a[2][0] * b[0][0]) + (a[2][1] * b[1][0]) + (a[2][2] * b[2][0]) + ... + (a[2][n] * b[n][0])
• result[k][0] = (a[k][0] * b[0][0]) + (a[k][1] * b[1][0]) + (a[k][2] * b[2][0]) + ... + (a[k][n] * b[n][0])

 

• 결론 - result[i][j] = (a[i][0] * b[0][j]) + (a[i][1] * b[1][j]) + (a[i][2] * b[2][j]) + ... + (a[i][n] * b[n][j])
• 삼중 for문 쓰면 되겠다!

---

3. 코드

 

테스트 코드

import static org.hamcrest.CoreMatchers.is;
import static org.junit.Assert.*;

import org.junit.Test;

public class KataTest {

  @Test
  public void testWhenInputIs2x2() {
    int[][] a = {
        {9, 7},
        {0, 1}
    };
    int[][] b = {
        {1, 1},
        {4, 12}
    };
    int[][] expected = {
        {37, 93},
        {4, 12}
    };

    assertThat(Kata.matrixMultiplication(a, b), is(expected));
  }

  @Test
  public void testWhenInputIs3x3() {
    int[][] a = {
        {1, 2, 3},
        {3, 2, 1},
        {2, 1, 3}
    };
    int[][] b = {
        {4, 5, 6},
        {6, 5, 4},
        {4, 6, 5}
    };
    int[][] expected = {
        {28, 33, 29},
        {28, 31, 31},
        {26, 33, 31}
    };

    assertThat(Kata.matrixMultiplication(a, b), is(expected));
  }
}

실제 코드

public class Kata {

  public static int[][] matrixMultiplication(int[][] a, int[][] b) {
    int[][] c = new int[a.length][a.length];
    int length = a.length;

    for (int i = 0; i < a.length; i++) {
      for (int j = 0; j < b.length; j++) {
        for (int k = 0; k < a.length; k++) {
          c[i][j] += a[i][k] * b[k][j];
        }
      }
    }

    return c;
  }
}

---

4. 느낀 점

• 문제 처음 볼땐 막막했는데 직접 써내려가니까 쉽게 풀렸다.
• 행렬 곱 코드정도는 최대공약수, 최소공배수처럼 그냥 외워두면 편할것같아서 정리한다.