[종만북] 행렬의 거듭제곱

||문제 이해

자연수 m이 주어질 때, 행렬^m 을 구하라

---

||해결 계획

분할 정복을 사용한다.

 

1. 먼저 재귀의 초기형을 짜본다.

Pow는 행렬mat의 m거듭제곱을 반환해 준다! 라고 믿는다

 

 

2. 그리고 m이 짝수일 경우와 홀수일 경우가 다른데 일단 짝수로 생각해보자

행렬의 짝수 거듭제곱인 A^4를 풀어보면 이렇다.

A^4 = A * A * A * A

이 식은 행렬 A의 4거듭제곱이니 Pow(A, 4)와 같다!

 

곱셈은 자리를 변경해도, 어떤것부터 곱하던지 값은 항상 똑같기에 분할하기 편하게 반으로 나누어보자

A^4 = (A * A) * (A * A) = A^2 * A^2

이렇게 되면 저 하나의 A^2는 Pow(A,2)로도 가능하다!

즉, A^4 = Pow(A, 2) * Pow(A, 2) 이다.

그럼 최종의 최종은 Pow(A,4) = Pow(A, 2) * Pow(A, 2) 일 것이다.

 

하지만 이렇게 되면 사실 분할정복의 의미가 없다.

분할정복을 정리하면서 깨달은건데

큰 그림만 놓고보면 사실 일반 재귀와 분할정복의 재귀 호출 수는 똑같다.

하나의 뭉텅이가 재귀 한번인데 각 개수를 세보면 11개로 똑같다.

근데 이 문제에서의 분할 정복이 메리트가 있는 건

※모든 분할정복이 그렇다는 건 아님

분할했을 때 A뭉텅이, B뭉텅이가 나온다고 하면

A뭉텅이의 재귀 값으로 B뭉텅이를 재귀호출하지 않고 알 수 있어서가 아닐까 싶다.

암튼 지금까지 경험상은 그렇다.

 

그래서 분할정복을 사용하려면 코드는 이렇게 되어야한다.

 

 

3. 이제 짝수는 되었으니 간단한 홀수를 추가한다.

A^5 = A * A^4 인건 당연한 사실

즉, A * Pow(A, A-1)로 홀수거듭제곱을 알 수 있다.

 

 

4. Base case를 추가해주면 완성이다.

---

||구현

Matrix Pow(Matrix mat, int m)
{
	//base case, 최소의 부분문제이므로 m이 1일때이다.
	if (m == 1) return mat;

	//홀수일 때의 답 반환
	if (m & 0x1) return mat * Pow(mat, m - 1);

	//m이 짝수일 때의 답 반환
	Matrix half = Pow(mat, m / 2);
	return half * 2;
}

---

||되돌아보기

책에서는 홀수일때 다른 방법도 제시했는데

pow(A, m/2) * pow(A, m/2 + 1) 이다.

내가 작성한 짝수일때 pow(A, m/2) * pow(A, m/2)와 같은 경우다.

 

이것도 마찬가지로 재귀호출양이 훨씬 많다.

하지만 이 방식이 더 빠르게 답을 도출하는 방법이 있는데

바로 동적계획법(DP)이다.

 

근데 이말을 듣고 생각해보니까 분할하는 여러 방법이 있겠다 싶었다.

그래서 무조건 반이아닌 좀 더 효율적인 분할방법을 찾아보려고도 해야겠다!

 

dp는 아직 내가 자신있게 풀수있는건 아니여서 얼른 속도내서 뒷장에서 공부해야겠다 = ~ =

 

암튼 이번 문제를 정리하면서 분할정복이 왜 재귀와 차이가 나는지 깨달았다. 

이렇게 좀 논리적인 코드를 작성하려고 노력하다보니까 예전보다 재귀 작성하기가 쉬워졌고

앞으로도 항상 더 논리적인 코드를 짜려고 노력해야겠다.