파이썬 행렬 곱셈, 거듭제곱 구하기

파이썬 행렬

알고리즘 문제를 풀 때 시간 복잡도를 줄이기 위해 행렬의 거듭제곱을 사용하는 경우가 있습니다. 대표적으로 피보나치 수열의 가장 빠른 시간 복잡도가 O(LogN)이 행렬로 구현할 수 있습니다. 피보나치와 행렬에 대한 내용은 자세한 내용은 아래 링크를 참조해주세요.

[CS/알고리즘] - 피보나치 파이썬으로 구하는 3가지 알고리즘

피보나치 파이썬으로 구하는 3가지 알고리즘

 

이렇게 가끔씩 행렬의 곱셈을 사용하는데... 이게 자주 사용하지 않는 3개의 중첩된 for문을 사용하다보니까 구현할 때 저는 매우 스트레스를 받습니다...;; 저만 그런 것 일수도 있지만... 3중 중첩 for문 부터는 미쳐버립니다 ㅎㅎ. 그래서 정리하는 차원에서 파이썬으로 행렬의 곱셈을 쉽게 이해하기 위한 방법을 공유하고자 합니다.

 

 

행렬 곱셈의 특성

두개의 행렬을 곱했을 때 앞의 행렬 행, 뒤의 행렬 열을 기준으로 새로운 행렬이 만들어 집니다.

 

def matrix_mult(A, B):
    temp = [[0] * (len(A)) for _ in range(len(B[0]))]
    ...
    ...
    return temp

위의 특성에 따라 코드상에서 곱셈을 통해 반환될 행렬의 크기는 앞의 행렬인 A의 행과 뒤의 행렬인 B의 열로 새로운 크기의 행렬을 만들어준다.

 

 

행렬의 곱셈을 하나씩 다 풀어보면 위와 같이 풀 수 있다. 이거를 보면서 숫자의 패턴을 막 확인하고 하면 결국에는 결과를 얻을 수 있기는 한데... 눈에 잘 안들어 옵니다. 그래서 이거를 i, j, k 3개의 중첩 for문을 사용한다고 할 때 아래와 같은 패턴을 만들 수 있습니다.

 

i, j, k 순서대로 중첩이 들어가고 순회 방식을 보고 비교해보면 어떻게 곱셈이 이루어지는지 확인할 수 있다. 그냥 머리속으로 생각하는 것보다 이렇게 그림을 그려가면서 어떻게 로직을 만들어야할지 직접 눈으로 보면 훨씬 더 쉽게 다가갈 수 있다.

 

 

파이썬 행렬 곱셉 코드

def matrix_mult(A, B):
    temp = [[0] * (len(A)) for _ in range(len(B[0]))]
    for i in range(len(A)):
        for j in range(len(A[0])):
            for k in range(len(B[0])):
                temp[i][k] += A[i][j] * B[j][k]
    return temp

i의 범위를 A의 행, j의 범위를 A의 열로 하거나 B의 행, k는 B의 열로 지정한다. 그림의 내용을 그대로 코드로 바꾸니 훨씬 쉽게 코드를 작성할 수 있다.

 

 

파이썬 행렬 거듭 제곱

행렬의 곱셈만 이용하는 것보다 대부분 행렬의 거듭제곱을 이용한 알고리즘을 이용한다. 그래서 사실 행과 열의 크기가 같은 정사각 행렬을 대부분 사용해서 i, j, k의 크기가 모두 같게 하는 경우가 많다.

 

파이썬 행렬 거듭 제곱 코드

def matrix_mult(A, B):
    temp = [[0] * (len(A)) for _ in range(len(B[0]))]
    for i in range(len(A)):
        for j in range(len(A[0])):
            for k in range(len(B[0])):
                temp[i][k] += A[i][j] * B[j][k]
    return temp


def matrix_pow(A, n):
    if n == 1:
        return A
    if n % 2 == 0:
        temp = matrix_pow(A, n//2)
        return matrix_mult(temp, temp)
    else:
        temp = matrix_pow(A, n-1)
        return matrix_mult(temp, A)

행렬의 곱셈을 이용해서 거듭제곱을 구할 수 있다. 재귀함수를 이용해서 제곱하는 행렬까지 내려오게하고 제곱수가 짝수인 경우 같은 행렬을 곱해 제곱시키고 홀수인 경우는 A 행렬 자신을 곱해서 해결한다.