행렬 제곱

문제

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

입력

첫째 줄에 행렬의 크기 N과 B가 주어진다. (2 ≤ N ≤ 5, 1 ≤ B ≤ 100,000,000,000)

둘째 줄부터 N개의 줄에 행렬의 각 원소가 주어진다. 행렬의 각 원소는 1,000보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄부터 N개의 줄에 걸쳐 행렬 A를 B제곱한 결과를 출력한다.

예제 입력

3 3
1 2 3
4 5 6
7 8 9

예제 출력

468 576 684
62 305 548
656 34 412

행렬 A의 B제곱을 구하고, 각 원소를 1000으로 나눈 나머지를 출력하는 문제다.

먼저 입력을 받고 각 원소를 1000으로 나눈 나머지를 넣어줬다. 행렬을 m번 곱한 값을 저장하기 위해 save라는 dictionary를 만들어 주고 1에 우리가 입력받은 matrix를 저장해준다. [포스팅을 하다가 알게 되었는데 동적 프로그래밍을 이용한 방법이었다.]

multiple 함수로 연산을 한다. 이때, m의 값을 확인한 후 이 값이 save안에 이미 저장되어 있으면 바로 값을 리턴해주고, save 안에 저장되어있지 않으면 m//2와 m-m//2로 더 작게 분할해 재귀함수를 호출한다. m//2와 m-m//2에 대한 값을 호출받았으면 추가로 연산을 한 후 save[m]에 저장했다.


for x in multiple(n,m):
    for i in x:
        print(i,end=' ')
    print()

이전까지는 항상 행렬에 대한 출력을 위와 같이 해왔었다. 포스팅을 하다가 알게된 사실인데 아래와 같이 배열앞에 * 을 붙여 동일한 출력을 얻어낼 수 있다고 한다.

for row in result:
    print(*row)


  • 채점을 하는데 계속 8~90프로 진행되다가 ‘틀렸습니다.’가 떠서 고민했었다. 동일한 문제를 겪는 사람은 아래와 같은 테스트 케이스를 고려해보길 바란다.
 2 1
 1000 1000
 1000 1000


Code

import sys
n,m=map(int,sys.stdin.readline().split())
matrix=[list(map(int,sys.stdin.readline().split())) for _ in range(n)]

for i in range(n):
    for j in range(n):
        matrix[i][j]= matrix[i][j]%1000

#행렬을 n 번 곱한 값을 save[n]에 저장
save=dict()
save[1]=matrix

def multiple(n,m):
    # 행렬을 m번 연산한 값이 이미 저장되어있으면 바로 return
    if m in save:
        return save[m]
    else:
        #저장되어있지 않을 경우 더 작은 값에 대해 재귀 호출을 한다.
        lista=multiple(n,m//2)
        listb=multiple(n,m-m//2)
        matrix=list([0 for _ in range(n)] for _ in range(n))

        for i in range(n):
            for j in range(n):
                matrix[i][j]=0
                for x in range(n):
                    matrix[i][j]+=lista[i][x]*listb[x][j]
                matrix[i][j]%=1000

        save[m]=matrix
        return save[m]
#출력
for x in multiple(n,m):
    for i in x:
        print(i,end=' ')
    print()


Improved

다른 블로그에서 B를 이진수로 변환시켜 푸는 코드를 발견해 가져와 보았다. 10^8을 넣어봐도 굉장히 빠르게 계산되는 모습을 볼 수 있다. Reference

파이썬의 빌트인 함수 bin에 대해서 간단히 알아보자.

B = bin(10)
print(B, type(B))
print(help(bin))

위 코드를 출력하면

0b1010 <class 'str'>
Help on built-in function bin in module builtins:

bin(number, /)
    Return the binary representation of an integer.

    >>> bin(2796202)
    '0b1010101010101010101010'


10은 이진수로 1010이다. 파이썬의 bin함수는 해당 integer를 이진수로 변환하고, 앞에 0b가 더해진 string의 형태로 return을 함을 알 수 있다. ‘0b’는 접두어 인데, 파이썬에서는 기본적으로 10진수 형태로 숫자를 표현하기 때문에 10진수 외의 다른 진수의 형태로 숫자를 표현하기 위해서는 앞에 접두어를 붙이는 것이다. b는 binary의 b이다.

그래서 아래의 코드에서는 접두어를 제거해 주기 위해

B = bin(B)[2:]

를 사용했다.

내장함수 format()을 사용하면 접두어를 제외하고 다른 진수의 문자열로 바꿀수도 있다. Reference

print(format(10,'b'))
>>1010


Code

import sys
#행렬 곱셈 함수
def matrix_mul(a, b):
    result = [[0]* N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            for k in range(N):
                result[i][j] += a[i][k] * b[k][j]

    for i in range(N):
        for j in range(N):
            result[i][j] %= 1000

    return result


#2진법으로 변환하여 분할정복 실행
N, B = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(N)]
B = bin(B)[2:] #2진법으로 변환

#단위 행렬
identity_matrix = [[1 if i == j else 0 for i in range(N)] for j in range(N)]

#2진법 자릿수 만큼 제곱 & 제곱한 행렬 끼리 곱해줌
result = identity_matrix[:]
for i in range(len(B)):
    if B[-i-1] == '1':
        while i != 0:
            matrix = matrix_mul(matrix, matrix)
            i -= 1
        result = matrix_mul(result, matrix)

for row in result:
    print(*row)


이 문제를 풀면서 동적 프로그래밍과 분할 정복이 뭐가 다른지 궁금증이 생겼다. 한번도 깊이 생각해보지 않았던 문제였다.

분할 정복 - Divide & Conquer

“분할 정복법은 여러 알고리즘의 기본이 되는 해결 방법으로, 기본적으로는 엄청나게 크고 방대한 문제를 조금씩 조금씩 나눠가면서 용이하게 풀 수 있는 문제 단위로 나눈 다음 그것들을 다시 합쳐서 해결하자는 개념에서 출발하였다.” 대표적으로 병합 정렬이 있다. Reference

  • 분할: 문제를 동일한 유형의 여러 하위 문제로 나눈다.
  • 정복: 가장 작은 단위의 하위 문제를 해결하여 정복한다.
  • 조합: 하위 문제에 대한 결과를 원래 문제에 대한 결과로 조합한다.

동적 프로그래밍 - Dynamic Programming

“동적 프로그래밍 어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해를 활용하는 방식의 알고리즘을 총칭한다. - 메모이제이션 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법이다.” Reference

이처럼 동적 프로그래밍에서는 여러개의 작은 문제들로 나눈 후, 이들을 풀 때 같은 문제에 대해 매번 계산하지 않도록 메모이제이션을 사용해 값을 저장했다가 재사용한다.(과거에 구한 해를 활용한다.)

분할 정복과 동적 프로그래밍 방식 모두 하나의 문제를 부분 문제로 나눠 계산한 후 합쳐 문제의 답을 구한다는 공통점이 있다. 동적 프로그래밍은 메모이제이션을 통해 부분 문제의 정답을 저장해놓고 사용한다는 차이점이 있다.

Crepe

내 첫번째 코드는 save에 행렬끼리 n번 곱한 값을 save[n]에 저장해두며 사용하고 있다. 메모이제이션을 사용해 동적 프로그래밍을 이용한 것이다.

이와 다르게 다른 분의 블로그에서 가져온 코드는 별도로 메모이제이션을 사용하지 않고 이진법을 활용해 계산했다.

[다시 풀어보기] ✔ - 2020.10.25 ✔ - 2020.12.17