코딩테스트/프로그래머스 level 2

[프로그래머스 level_2] 행렬의 곱셈 for JAVA

냠냠:) 2021. 6. 24. 22:13

https://programmers.co.kr/learn/courses/30/lessons/12949

 

코딩테스트 연습 - 행렬의 곱셈

[[2, 3, 2], [4, 2, 4], [3, 1, 4]] [[5, 4, 3], [2, 4, 1], [3, 1, 1]] [[22, 22, 11], [36, 28, 18], [29, 20, 14]]

programmers.co.kr

[문제 설명]

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

 

제한 조건

  • 행렬 arr1, arr2의 행과 열의 길이는 2 이상 100 이하입니다.
  • 행렬 arr1, arr2의 원소는 -10 이상 20 이하인 자연수입니다.
  • 곱할 수 있는 배열만 주어집니다.

입출력 예

arr1 arr2 return
[[1, 4], [3, 2], [4, 1]] [[3, 3], [3, 3]] [[15, 15], [15, 15], [15, 15]]
[[2, 3, 2], [4, 2, 4], [3, 1, 4]] [[5, 4, 3], [2, 4, 1], [3, 1, 1]] [[22, 22, 11], [36, 28, 18], [29, 20, 14]]

 

[풀이]

문제를 풀기 앞서 행렬의 특징을 조금 이해할 필요가 있다.

 

A행렬 X B행렬이라 했을 때,

 

A행렬의 행 개수 X B행렬의 열 개수 = 결과행렬의 크기

 

예를들면

1 2
3 4
5 6

A행렬 (3x2)에

 

1 2
3 4

B행렬(2x2)을 곱하면 3x2행렬이 나온다는 말이다.

 

또한 행렬곱셈조건에는 A행렬(3x2)의 과 B행렬(2x2)의 개수가 같아야 한다는 조건이 있다.

 

 

 

문제로 다시 돌아와서, 결과행렬은 우리는 A행 X B열의 크기의 행렬을 구하는 것이고

 

각 요소는 행렬 곱셈법칙을 기반으로 더해진다.

 

R[0][0] = A[0][0] * B[0][0] + A[0][1] * B[1][0]

R[0][1] = A[0][0] * B[0][1] + A[0][1] * B[1][1]

....

등과 같이 계산이 되며(행렬을 한 번 곱해보면 이해된다), 

 

이때 코드로써의 반복문을 고려해볼 수 있다.

 

A행렬의 i로 B행렬의 j로  R[i][j]로 결과행렬을 만들 수 있고

 

중간에 필요한 연산(EX. A[0][0] * B[0][0] + A[0][1] * B[1][0])은 

 

우리가 아까 말했던 A행렬의 열과 B행렬의 행의 개수가 같다는 조건을 사용한다

 

 

 

예를 들어, R[0][0] = A[0][0] * B[0][0] + A[0][1] * B[1][0]일 때

 

조금 문제에 관심을 기울여서 패턴을 찾아본다면

 

A[i][0] * B[0][j] + A[i][1] * B[1][j]를 찾을 수 있고

 

이때 이 식을 반으로 잘라서 생각해본다면

 

R[0][0] += A[i][0] * B[0][j]

R[0][0] += A[i][1] * B[1][j]

 

임을 알 수 있다.

 

i와 j를 제외한 수는 0~1까지 증가함을 알 수 있고 이 증가수는 아까 설명했던 A행렬의 열과 B행렬의 행의 개수이다.

 

즉, R[i][j] = A[i][K] * B[K][j] + A[i][K] * B[K][j] 이면서

 

for(i, A행 개수) :

    for(j, B열 개수) :

        for(k, A열 개수 or B행 개수):

             R[i][j] = A[i][K] * B[K][j] + A[i][K] * B[K][j]

임을 알 수 있다.

 

설명으로 이해가 안 된다면, 손으로 패턴을 찾아보는 것을 추천한다.

[코드]

/**
 * level 2
 * 행렬의 곱셈
 * https://programmers.co.kr/learn/courses/30/lessons/12949
 */
public int[][] solution(int[][] arr1, int[][] arr2) {
	int[][] matrix = new int[arr1.length][arr2[0].length];
	
	for(int i = 0; i < arr1.length; i++) {
		for(int j = 0; j < arr2[0].length; j++) {
			int temp = 0;
			for(int k = 0; k < arr2.length; k++) {
				temp += arr1[i][k] * arr2[k][j];
			}
			matrix[i][j] = temp; 
		}
	}
	
	return matrix;
}

프로그래머스 테스트케이스 통과

반응형