[Python] 행렬의 곱셈

먼저 행렬을 곱하기 위해서는 앞 행렬의 열의 수와 뒤 행렬의 행의 수가 같아야 됩니다. 이러한 조건이 맞다면 행렬의 곱셈의 결과 크기는 (앞 행렬의 행의 수)×(뒤 행렬의 열의 수)가 됩니다. 즉, 앞 행렬이 m X n 이고 뒤 행렬이 n X r 인 경우 곱은 m X r 크기의 행렬이 됩니다.

예를 들어, 2x2 행렬의 곱은 아래와 같습니다.

이를 식으로 표현하면 아래와 같습니다.

따라서 행렬의 곱셈의 복잡도는 O(n^3)입니다.

아래는 복잡도 O(n^3)의 행렬의 곱셈을 구하는 파이썬 코드입니다.

def solution(arr1, arr2): answer = [] for i in range(0, len(arr1)): temp_row = [] for j in range(0, len(arr2[0])): value = 0 for k in range(0, len(arr1[0])): value += arr1[i][k] * arr2[k][j] temp_row.append(value) answer.append(temp_row) return answer

이보다 빠른 행렬의 곱셈 알고리즘은 슈트라센 알고리즘 O(n^2807), 위노그라드 알고리즘 O(n^2.795), 코퍼스미스-위노그라드 알고리즘 O(n^2.3737) 등이 존재합니다.