[프로그래머스 2단계] 알고리즘 24. 행렬의 곱셈

문제 출처는 프로그래머스 알고리즘 연습 에서 볼 수 있습니다!(https://programmers.co.kr/learn/challenges)

알고리즘 24. 행렬의 곱셈

행렬의 곱셈은, 곱하려는 두 행렬의 어떤 행과 열을 기준으로, 좌측의 행렬은 해당되는 행, 우측의 행렬은 해당되는 열을 순서대로 곱한 값을 더한 값이 들어갑니다. 행렬을 곱하기 위해선 좌측 행렬의 열의 개수와 우측 행렬의 행의 개수가 같아야 합니다. 곱할 수 있는 두 행렬 A,B가 주어질 때, 행렬을 곱한 값을 출력하는 productMatrix 함수를 완성해 보세요.

class ProductMatrix {

    public int[][] productMatrix(int[][] A, int[][] B) {

        int[][] answer = null;

        return answer;

    }

    public static void main(String[] args) {

        ProductMatrix c = new ProductMatrix();

        int[][] a = { { 1, 2 }, { 2, 3 } };

        int[][] b = { { 3, 4 }, { 5, 6 } };

// 아래는 테스트로 출력해 보기 위한 코드입니다.

System.out.println("행렬의 곱셈 : " + c.productMatrix(a, b));

    }

}

풀이 :

 

행렬의 곱셈은 좌측 행렬의 열과 우측 행렬의 행의 길이가 같아야 가능하다. 또한 곱해진 행렬의 행은 좌측 행렬의 행 열은 우측 행렬의 열이다. 쉽게 수식으로 표현하면 다음과 같다.

A(I x J) X B(J x K) = C(I x K)

그리고 C의 원소는 다음 수식을 만족한다.

C[i][j] = (A[i][0] * B[0][j]) + (A[i][1] * B[1][j]) + (A[i][2] * B[2][j]) + ... + (A[i][k] * B[k][j]) 

여기서 k는 A의 열의 개수이자 B의 행의 개수인 J와 같다. 이것이 이 문제의 핵심이다. 나의 알고리즘은 다음과 같다.

1. 먼저 C (I X K) 배열을 미리 생성한다.
2. 그 후 행렬 곱셈 연산을 한다.

코드는 다음과 같다.

public int[][] productMatrix(int[][] A, int[][] B) {

    //1. 행렬 공간 만들기 A(I x J) X B(J x K) = C(I x K)

final int I = A.length, K = B[0].length;

final int J = A[0].length; //순회 공간 A의 행 B의 열

int[][] answer = new int[I][K];

//2. 행렬 곱셈

for(int i=0; i<I; i++)

for(int j=0; j<K; j++)

for(int k=0; k<J; k++)

answer[i][j] += (A[i][k] * B[k][j]);

     return answer;

}

 

사실 이 문제를 조금 더 세련되게 푸는 방법이 몇가지 더 있다. 가령 캐시 친화적인 코드를 작성하든가 함수형으로 풀어보든가 말이다. 이렇게 푼건 20분도 안되어 다 풀었는데 1시간 넘게 함수형으로 풀어보려고 고민하다가 실패했다. 아직까지 스트림API가 익숙치 않나 보다. 조금 더 열심히 공부해야겠다. 후에 스트림으로 푸는게 익숙해질 때 쯤 다시 한 번 풀어봐야겠다.