[백준 2740 파이썬] 행렬 곱셈 (브론즈1, 선형대수)

알고리즘 유형 : 선형대수
풀이 참고 없이 스스로 풀었나요? : O

https://www.acmicpc.net/problem/2740

소스 코드(파이썬)

N, M = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(N)]

M, K = map(int, input().split())
B = [list(map(int, input().split())) for _ in range(M)]

AxB = [[0]*K for _ in range(N)]
for row in range(N):
    for col in range(K):
        e = 0
        for i in range(M):
            e += A[row][i] * B[i][col]
        AxB[row][col] = e

for r in AxB:
    print(*r)

풀이 요약

1. 행렬의 곱셈을 할줄 안다면 구현만 하면 되는 문제이다.

   NxM, MxK 행렬을 곱하면 NxK 행렬이 된다.

   $\begin{bmatrix}1&4\\2&5\\3&2\end{bmatrix}\ X\ \begin{bmatrix}2&3&2\\3&4&1\end{bmatrix}\ =\ \begin{bmatrix}a&b&c\\d&e&f\\g&h&i\end{bmatrix}$

   
   NxK 행렬에서, 만약 NxK의 2행 3열의 값 f를 구하고자 한다면,

   앞의 행렬의 2행 벡터 (2, 5)

   뒤의 행렬의 3열 벡터 (2, 1)

   이 것에 대해, 첫 번째 요소, 두 번째 요소, ..., 를 매칭해서 곱하고 그 값들을 다 더해주면 그게 f다.

   f = 2x2 + 5x1 = 9

   이 때 Nxk의 u행 v열 값을 구할 때, 앞 행렬의 u행 벡터, 뒤 행렬의 v열 벡터를 이용해서 각 요소를 곱해주는 행위를 하기 때문에, u행 벡터의 크기, v열 벡터의 크기가 같아야 하고, 즉 앞 행렬의 열의 개수(행벡터의 크기가 됨), 뒤 행렬의 행의 개수가 같아야 곱이 정의 됨.

2. N과 K에 대해 이중 for문을 돌면서, 벡터의 크기 M만큼 for 돌면서 행벡터와 열벡터의 각 요소 곱의 더하기 값을 구해주고 결과 행렬에(2차원 리스트) 넣어주면 된다.

배운 점, 어려웠던 점

• 행렬의 곱셈에 대해서 이미 알고 있었어서 별 어려움 없던 문제였다.