[백준_분할정복] 2740번 - 행렬 곱셈 - 이해까지 도와주는 풀이

문제

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를 곱한 행렬을 출력한다. 행렬의 각 원소는 공백으로 구분한다.

 

예제 입력

3 2
1 2
3 4
5 6
2 3
-1 -2 0
0 0 3

 

 

예제 출력

-1 -2 6
-3 -6 12
-5 -10 18

 

 

 

풀이

 

이번 문제는 행렬의 곱 문제입니다. 전형적인 기본문제이니까, 꼭 습득하셔야 합니다.

 

어떻게 풀면 좋을까요? 핵심 아이디어는 다음과 같습니다. 

 

행렬의 곱은 각 원소를 곱해서 더하는 방식으로 이루어집니다. 

 

행렬 A와 B의 곱에서 결과 행렬 C의 각 원소를 계산한다고 가정하면 

행렬 A는  N x M 이며, 행렬 B의 크기는 M x K 입니다. 결과 행렬 C의 크기는 N x K가 됩니다.

 

 

결과 행렬 C의 각 원소 C[i][j]는 

 

C[i][j] = A[i][0] * B[0][j] + A[i][1] * B[1][j] + ... + A[i][M-1] * B[M-1][j]

즉, C[i][j]는 행렬 A의 i번째 행과 행렬 B의 j번째 열을 곱해서 합한 값입니다. 

 

이를 위해 이중 반복문을 사용하고 있습니다. 

# 행렬 A와 B를 곱함
for i in range(N):
    for j in range(K):
        for k in range(M):
            C[i][j] += A[i][k] * B[k][j]

 

첫 번째 반복문은 결과 행렬 C의 행을 나타내며, 두 번째 반복문은 결과 행렬 C의 열을 나타냅니다. 

 

그리고 세 번째 반복문은 행렬 A와 B의 각 원소를 순회하며 곱셈을 수행합니다.

따라서 위의 코드는 모든 C[i][j] 값을 계산하고 결과 행렬 C를 구성하는 과정을 수행합니다. 

 

이를 통해 두 행렬 A와 B의 곱을 구할 수 있습니다.

 

 

소스 코드

 

# 행렬 A의 크기 N과 M을 입력 받음
N, M = map(int, input().split())

# 행렬 A 입력 받음
A = []
for _ in range(N):
    row = list(map(int, input().split()))
    A.append(row)

# 행렬 B의 크기 M과 K를 입력 받음
M, K = map(int, input().split())

# 행렬 B 입력 받음
B = []
for _ in range(M):
    row = list(map(int, input().split()))
    B.append(row)

# 결과 행렬 C 초기화
C = [[0] * K for _ in range(N)]

# 행렬 A와 B를 곱함
for i in range(N):
    for j in range(K):
        for k in range(M):
            C[i][j] += A[i][k] * B[k][j]

# 결과 행렬 C 출력
for i in range(N):
    for j in range(K):
        print(C[i][j], end=' ')
    print()