[알고리즘] 백준. 행렬 제곱 #10830

백준 단계별로 풀어보기 분할 정복 카테고리의 문제 중 10830번 문제인 '행렬 제곱'문제를 풀어보았습니다. 

 

문제

크기가 N*N인 행렬A의 B제곱을 구하는 코드를 작성하라. 이때 $A^{B}$의 원소를 1000으로 나눈 나머지를 출력한다.

 

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

둘째 줄부터 N개의 줄과 N개의 행렬이 주어진다. 

 

#예시

2 5
1 2
3 4

로 주어지면

2 x 2 행렬

A = 1 2 
    3 4
    
A^5(B=5)를 구하면 된다.

 

 

접근법

첫번째 시도.

우선 B가 매우 큰 값이 올 수 있기 때문에 A의 B제곱에서 제곱 수인 B를 줄일 수 있는 방법을 고민했다. 즉, A를 B번 곱하는데, 이를 B보다 적게 곱하게 하고 싶었다. 

 

분할 정복 문제이기에 탈출 조건인 B=1인 case를 정의해 주고, B를 절반으로 나눠가며 재귀적으로 계산해 주도록 생각했다. 그러나 코드를 짜보니 시간초과가 떴다..ㅠㅠ 생각해 보니 연산 횟수가 그냥 곱했을 때랑 별 차이가 없었다. 

 

그냥 곱할 때(왼쪽)와 첫번째 생각한 방법(오른쪽). 둘 다 곱셈 횟수는 6번으로 차이가 없다. 

두번째 시도.

첫번째 방법을 살펴보면, 같은 결과값이 나왔을 때 이를 충분히 활용하지 못하고, 또 다시 연산한다. 예를 들어 $A^{2} * A^{2}$ 에서 A*A를 두 번이나 계산한다(좌항 한 번, 우항 한 번). 그래서 방법을 달리 접근해 보았다. 이처럼 B가 짝수인 경우에는 한 번만 계산하도록 하고 같은 값을 곱해주도록 하여 연산을 줄여보고자 했다. 또 홀수일 경우에는 $A^{B-1}*A$꼴로 변환하여 짝수 제곱과 A자신의 곱으로 연산하고자 하였다. 자신과 같은 값을 곱해주는 부분에서 재귀적으로 더 내려가지 않고 자신을 복제하여 연산하여 연산 횟수를 줄였다. 결과는 통과!

 

두번째 접근방법, 위의 예시에서는 4번 연산으로 횟수가 줄었다.

결과 코드

#입력값 받기
N, B = map(int, input().split())
mat = []
for i in range(N):
    mat.append(list(map(int, input().split())))

#행렬 출력
def printM(mat, N):
    for a in range(N):
        for b in range(N):
            print(mat[a][b]%1000, end = ' ')
        print()
        
        
#행렬 연산
def matmul(M, B):
    global N
    if B == 1:
        return M
    else:
        resM = [[0 for _ in range(N)] for _ in range(N)]
        if B%2 == 0: #B가 짝수
            X = matmul(M, B//2)
            for i in range(N):
                for j in range(N):
                    for k in range(N):
                        resM[i][j] += X[i][k] * X[k][j]
                    resM[i][j] %= 1000       

        else: #B가 1보다 큰 홀수 
            X = matmul(M, B-1) #M^(B-1) 과 M을 곱해준다.
            for i in range(N):
                for j in range(N):
                    for k in range(N):
                        resM[i][j] += X[i][k] * M[k][j]
                    resM[i][j] %= 1000                      
    
        return resM
        
resM = matmul(mat, B)

printM(resM, N)

 

행렬의 연산

더 좋은 연산법이 있는 지는 모르겠지만, 제가 알고있는 연산법은 for문을 3번 돌면서 연산하는 방식입니다. 

 

행렬의 제곱에 대해서만 식을 뽑아 보았는데, 일반적인 직사각행렬에 대해서도 일반화가 가능하다. 쨌든 이 문제는 행렬의 제곱에 대한 문제이니 이에 한정하여 분석하면, 맨 아래의 식이 나온다. 여기서 N은 행렬의 차수이다. 위의 예시에선 3차가 되겠다. 마지막 결과 식을 파이썬 코드로 표현하면 다음과 같다. 이는 위 결과 코드에서도 사용되었다. 

 

resM = [[0 for _ in range(N)] for _ in range(N)] # 행렬 정의, N은 행렬의 차수, 정방행렬임을 가정.
#resM의 행렬의 index를 참조하여 값을 더해주는 방식으로 작성한다.

위의 식을 코드로 표현한 형태
for i in range(N):
	for j in range(N):
		for k in range(N):
			resM[i][j] += X[i][k] * X[k][j]

 

나머지 연산

문제에서 값이 너무 커지는 걸 방지하기 위해 결과 값의 각 원소를 1000으로 나눈 나머지 값만을 제출하도록 하였다. 필자가 쓴 코드에는 행렬 곱셈을 하는 도중에 1000으로 나눈 값으로 계속 갱신해주었는데 이게 왜 가능한 지 살펴보고자 한다. 

우선, 행렬의 곱셈은 각 원소의 곱셈과 덧셈, 즉 선형 연산으로 이루어져 있다. Modular 연산, 나머지 연산을 적용하여도 곱셈과 덧셈은 그대로 유지되기에 행렬 곱셈 내부에서 나머지 연산으로 원소 값을 갱신해주어도 결과에 영향을 미치지 않는다. 아래 식을 통해 이를 확인해 볼 수 있다.

따라서 위의 설명처럼 덧셈, 곱셈에 대해 영향이 없음을 확인할 수 있다.