백준 2740 행렬곱셈

행렬곱셈 (백준 2740)

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

완전탐색 방식으로 풀었다
다만 ‘분할정복’이기에 관련 방식이 따로 존재하는지
조사를 해보았는데,

행렬의 크기를 2의 n승으로 만들고
‘슈트라센’ 알고리즘을 적용하는 방법이 존재한다고 한다

다만 해당 공식이 다소 복잡하며,
실제로 그것을 외워서 쓰는 것이 다소 난해해 보여

조사한 블로그의 링크만 올려두도록 한다

시간 복잡도를 O(n^3)에서 O(n^2)로 줄이며
이에 따라 최적화 등에 사용될 것 같은 알고리즘이다

https://izmirprogramming.tistory.com/13

Code

import sys

inp = sys.stdin.readline

n,m = map(int,inp().split())
aMatrix = [list(map(int,inp().split())) for _ in range(n)]
m,k = map(int,inp().split())
bMatrix = [list(map(int,inp().split())) for _ in range(m)]

transBM = []

for i in range(k):
    transBM.append([])
    for j in range(m):
        transBM[i].append(bMatrix[j][i])

result = []
for i in range(n):
    result.append([])
    for j in range(k):
        temp = 0
        for l in range(m):
            temp += aMatrix[i][l] * transBM[j][l]
        result[i].append(temp)

for i in range(n):
    print(*result[i])

해결 아이디어

1. 두 행렬을 받은 뒤,
   곱하기 위한 행렬을 뒤집어(transpose)
   해당 내용을 첫번째 행렬과 곱하는 방식
   
2. 이후, 뒤집힌 행렬과 첫번째 행렬을 곱한 수를 result 에 넣어준다