알고리즘 유도과정

행렬 곱셈 알고리즘 유도 과정.002.jpeg

행렬의 곱셈은 다음과 같은 성질을 같는다.

  • 행렬 A와 행렬 B가 곱해진다면 A의 열의 크기와 B의 행의 크기가 같다.
  • 행렬 A가 N x M의 크기를 가지고 행렬 B가 M x K의 크기를 갖는다면 A x B = C의 크기는 N x K이다.

행렬 곱셈 알고리즘 유도 과정.003.jpeg

행렬은 2차원 배열로 나타낼 수 있기 때문에 행(row)과 열(column)을 인덱스로 사용 할 수 있다.

이것을 1차원으로 나타내면 행렬 C를 수열이라고 생각 할 수 있다.

행렬 곱셈 알고리즘 유도 과정.003.jpeg

각 수열의 항은 위 처럼 계산되며 이것이 바로 행렬을 곱하는 과정이다.

상수 N, M, K는 햇갈리지 않게 대문자로 표기했다.

그리고 인덱스 변수 i, j, k는 소문자로 표기했다.

규칙을 살펴보면, 하나의 항을 계산하기 위해 곱셈이 M번 반복된다는 것을 알 수 있다. (인덱스 k)

다음으로 하나의 행을 모두 계산하기 위해 K번 반복된다는 것을 알 수 있다. (인덱스 j)

마지막으로 모든 행을 계산하기 위해 N번 반복된다는 것을 알 수 있다. (인덱스 i)

행렬 곱셈 알고리즘 유도 과정.005.jpeg

따라서 수열 $C_{ij}$의 일반항은 위와 같이 구할 수 있다.

이를 그대로 코드로 옮기면 행렬 곱의 계산 알고리즘이 된다.

행렬 곱셈 문제 (백준 2740번)

문제

NM크기의 행렬 A와 MK크기의 행렬 B가 주어졌을 때, 두 행렬을 곱하는 프로그램을 작성하시오.

입력

첫째 줄에 행렬 A의 크기 N 과 M이 주어진다. 둘째 줄부터 N개의 줄에 행렬 A의 원소 M개가 순서대로 주어진다. 그 다음 줄에는 행렬 B의 크기 M과 K가 주어진다. 이어서 M개의 줄에 행렬 B의 원소 K개가 차례대로 주어진다. N과 M, 그리고 K는 100보다 작거나 같고, 행렬의 원소는 절댓값이 100보다 작거나 같은 정수이다.

출력

첫째 줄부터 N개의 줄에 행렬 A와 B를 곱한 행렬을 출력한다. 행렬의 각 원소는 공백으로 구분한다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
N, M = map(int, input().split())
K = 0

# N x M | M x K matrix
A, B = [], []

for i in range(N):
    A.append(list(map(int, input().split())))

M, K = map(int, input().split())

for i in range(M):
    B.append(list(map(int, input().split())))

# N x K matrix
C = [[0] * K for _ in range(N)]

# C[i][j] = A[i][k_0] * A[k_0][j] + A[i][k_1] * A[k_1][j] + ... + A[i][k_m-1] * A[k_m-1][j]
for i in range(N):
    for j in range(K):
        for k in range(M):
            C[i][j] += A[i][k] * B[k][j]

for i in range(N):
    for j in range(K):
        print(C[i][j], end=" ")
    print("")

복잡도 분석

일반적으로 루프가 한번 중첩 될때마다 $O(n)$ 만큼의 시간 복잡도를 갖는다.

따라서 약 $O(n^3)$의 복잡도를 갖는다고 할 수 있다.