Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

20. 분할 정복

재귀를 응용하는 알고리즘, 분할 정복을 익혀 봅시다.

Java / Python

6. 행렬 곱셈

2740번

행렬의 거듭제곱을 계산하기 전에 먼저 풀어야 할 문제

이번 문제는 NxM크기의 행렬 A와 MxK크기의 행렬 B가 주어졌을 때, 두 행렬을 곱하는 프로그램을 작성하는 문제입니다.

• Java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
 
public class Main {
 
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		// A행렬 입력
		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(), " ");
		
		// B행렬 입력 
		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());
			}
		}
				
		// 행렬 계산 및 출력
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < K; j++) {
				int sum = 0;
				for(int k = 0; k < M; k++) {
					sum += A[i][k] * B[k][j];
				}
				sb.append(sum).append(' ');
			}
			sb.append('\n');
		}
		System.out.println(sb);
	}
}

• Python

import sys
N, M = map(int, sys.stdin.readline().split())
A = []
for _ in range(N):
    A.append(list(map(int, sys.stdin.readline().split())))

M, K = map(int, sys.stdin.readline().split())
B = []
for _ in range(M):
    B.append(list(map(int, sys.stdin.readline().split())))


C = [[0 for _ in range(K)] for _ in range(N)]

for n in range(N):
    for k in range(K):
        for m in range(M):
            C[n][k] += A[n][m] * B[m][k]

#출력
for i in C:
    for j in i:
        print(j, end = ' ')
    print()