[알고리즘] 행렬 곱셈, 행렬 제곱

행렬 제곱의 문제를 풀어야하는데, 행렬 곱셈을 하는 법부터 정확히 알지 못 했기 때문에 정리하는 글이다.

1. 2740: 행렬 곱셈

문제

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

 

=> 행렬의 곱셈 공식에 의해서 N*M, M*K 행렬을 곱하면 N*K 행렬이 된다.

오른쪽 사진에 의하면, 3 x 2 행렬과 2 x 3 행렬이다. 

3 x 2 행렬과 2 x 3 행렬을 곱하면 3 x 3 행렬이 만들어진다. 두 행렬을 곱하면 위의 왼쪽 사진과 같은 결과가 나온다.

 

1) N과 K에 대해 이중 for문을 돌면서,

2) 벡터의 크기 M만큼 for 돌면서 행벡터와 열벡터의 각 요소 곱의 더하기 값을 구해주고

3)결과 행렬에(2차원 리스트) 넣어주면 된다.

import sys
sys.stdin = open('input.txt', 'r')
# N행, M열의 행렬
N, M = map(int, sys.stdin.readline().split())
A = [list(map(int, sys.stdin.readline().split())) for i in range(N)]

# M행, K열의 행렬
M, K = map(int, sys.stdin.readline().split())
B = [list(map(int, sys.stdin.readline().split())) for i in range(M)]

# N*M, M*K 행렬을 곱하면 N*K 행렬이 된다.
# N은 행, K는 열이기 때문
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)

# 입력
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

2. 10830: 행렬 제곱

문제

크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다.

 

[풀이]

1. 행렬 간의 곱셈을 구현 => 크기가 N*N인 행렬 A

2. 행렬을 큰 수로 거듭제곱하게 되면 계산이 오래 걸리므로, 분할하여 해결해야한다. => 분할 정복

3. 1000으로 나눈 나머지 출력을 구현

 

먼저 행렬 간의 곱셈이 우선시 되어야 B를 거듭제곱하기 때문에 곱셈 연산부터 구현한다. calc의 마지막 줄쯤 new_arr[i][j] %= 1000는 현재 입력 행렬([[1, 2], [3, 4]])의 각 원소가 1000보다 작기 때문에 영향을 미치지 않는다.

곱셈이 잘 되는지 확인하기 위해서 [[1, 2], [3, 4]] 행렬과 [[1, 2], [3, 4]] 행렬을 곱셈한 결과이다.

각 원소가 1000이 넘는 배열이 들어왔을 때 경우에만 나머지를 꺼내지 않고 애초에 1000을 나누어 준다.

결국에 구하고자 하는 바는 크기가 N*N인 행렬 A를 B제곱한 것을 1000으로 나눈 것이다. 그렇다면 행렬 A의 B제곱을 1000으로 나눌 수 있어야하는 것인데, 결론적으로는 나눌 수 있다. 나머지 정리를 활용하면 된다.  

나머지 연산에 의해, 위와 같은 항등식이 성립한다.

나머지 정리에 의해서 위와 같은 연산이 증명되며 분배할 수 있다. 이는 행렬 간의 곱셈에도 적용된다.

위 개념을 사용하면 거듭제곱을 분할해서 계산할 수 있게 된다.

예를 들면, (A**10) % 1000 을 ( ((A**5) % 1000) * ((A**5) % 1000) ) % 1000 과 같이 풀어서 계산할 수 있는 것이다.

# 10830: 행렬 제곱
# 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 
# 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다.

import sys
sys.stdin = open('input.txt', 'r')
# 크기가 N*N인 행렬 A, B제곱
N, B = map(int, sys.stdin.readline().split())
# N개의 줄에 행렬의 각 원소 주어짐
A = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]    

# 받을 때부터 행렬의 각 원소가 나머지로 들어감
for i in range(N):
    for j in range(N):
        A[i][j] %= 1000

# 분할정복을 통합 거듭제곱
def solution(a, b):
    if b == 1:
        return a
    sub_a = solution(a, b//2)
    if b % 2 == 1:  # 제곱하는 숫자가 홀수인 경우
        return calc(calc(sub_a, sub_a), a)
    else:   # 제곱하는 숫자가 짝수인 경우
        return calc(sub_a, sub_a)
    
# 행렬 간의 곱셈하는 함수
def calc(ma, mb):
    n = len(ma)
    new_arr = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            for k in range(n):
               new_arr[i][j] += ma[i][k] * mb[k][j]
            new_arr[i][j] %= 1000
    return new_arr

answer = solution(A, B)

for a in answer:
    for i in a:
        sys.stdout.write(f'{i} ')
    sys.stdout.write('\n')

나만 알아봐도 이해했으니 됐다.........

---

공부 참고 블로그:

From 우리조 JH(교수님🤗) 코드 .. 

From 우리조였던 JH 백준 행렬 제곱 풀이: https://prodyou.tistory.com/14