[Java+Python]2740번, 행렬 곱셈

목차

 

분할 정복 단계

 

[Java+Python]2630번, 색종이 만들기

[Java+Python]1992번, 쿼드 트리

[Java+Python]1780번, 종이의 개수

[Java+Python]1629번, 곱셈

[Java+Python]11401번, 이항 계수 3

[Java+Python]10830번, 행렬 제곱

[Java+Python]11444번, 피보나치 수 6

[Java+Python]6549번, 히스토그램에서 가장 큰 직사각형

 

문제

 

N*M크기의 행렬 A와 M*K크기의 행렬 B가 주어졌을 때, 두 행렬을 곱하는 프로그램을 작성하시오.

 

입력

 

첫째 줄에 행렬 A의 크기 N과 M이 주어진다. 

둘째 줄부터 N개의 줄에 행렬 A의 원소 M개가 순서대로 주어진다. 

그다음 줄에는 행렬 B의 크기 M과 K가 주어진다. 

이어서 M개의 줄에 행렬 B의 원소 K개가 차례대로 주어진다. 

N과 M, 그리고 K는 100보다 작거나 같고, 행렬의 원소는 절댓값이 100보다 작거나 같은 정수이다.

 

출력

 

첫째 줄부터 N개의 줄에 행렬 A와 B를 곱한 행렬을 출력한다. 행렬의 각 원소는 공백으로 구분한다.

 

풀이

 

갑작스럽게도 분할정복과는 상관없는 문제가 등장했다. 

 

아마도 이어지는 행렬의 거듭제곱이나 피보나치 수를 빠르게 구하는 문제를 풀기 위해

 

행렬의 곱셈이라는 개념이 필요한 것 같다.

 

행렬 곱에 대한 기본적인 사실만 짚고 넘어가자면

 

• N*M 행렬과 L*K 행렬을 곱하는 경우, M과 L의 크기가 같지 않으면 곱할 수 없다.
• N*M 행렬과 M*K 행렬을 곱한 결과는 N*K의 크기를 가지게 된다.
• A, B 행렬을 곱한 결과를 AB라고 했을 때, 행렬 곱은 다음과 같이 계산된다.
  $(AB)_{nk}​=∑_k​A_{nm}​B_{mk}$​

위와같이 다소 복잡하게 정의되는 이유는 선형대수학 강의를 들으면 알 수 있지만, 여기선 중요하지 않다.

 

문제는 주어진 값으로 행렬을 초기화 한 뒤, 공식에 따라 곱하고 출력하는 것으로 끝난다.

 

Java

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Prob2740 {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int[][] A = new int[n][m];

		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < m; j++) {
				A[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		st = new StringTokenizer(br.readLine(), " ");

		m = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		int[][] B = new int[m][k];

		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < k; j++) {
				B[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		StringBuilder sb = new StringBuilder();

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < k; j++) {
				int sum = 0;
				for (int l = 0; l < m; l++) {
					sum += A[i][l] * B[l][j];
				}
				sb.append(sum).append(' ');
			}
			sb.append('\n');
		}

		System.out.println(sb);
	}
}

 

Python

 

import sys

n, m = map(int, sys.stdin.readline().rstrip().split())
A = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(n)]
m, k = map(int, sys.stdin.readline().rstrip().split())
B = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(m)]

result = ''

for i in range(n):
    for j in range(k):
        sum = 0
        for l in range(m):
            sum += A[i][l] * B[l][j]
        result += str(sum) + ' '
    result += '\n'

print(result)

 

Performance

 

파이썬은 자바에 비해 1/3밖에 되지 않는 코드 길이를 자랑한다.