[BOJ] 백준 10830 행렬 제곱 (JAVA)

분할정복!

📑 문제

백준 10830 행렬 제곱

---

🌱 아이디어

분할정복을 이용한 행렬제곱 문제, 큰 문제를 작은 단위로 나눠서 풀어보자

 

분할 정복의 가장 기본적인 개념은 큰 문제를 작은 단위로 나눠서 푸는 것이다..

 

예를 들면 N^8 은 N*N*N*N*N*N*N*N 이다. 즉 N을 8번 곱해야 한다.  분할 정복을 통해 작은 단위로 나눠서 bottom up 방식으로 푼다면  (((N^2)^2)^2) 3번만 연산하면 된다. 이는 O(logn)의 시간복잡도를 가지며

 

N^B, B가 클수록 좋은 성능을 보여준다. 

 

그리고 행렬 A와 행렬 B를 곱한다면

 

A =

1	2
3	4

 

B =

5	6
7	8

 

 

A X B =

1*5+2*7	1*6+2*8
3*5+4*7	3*5+4*8

 

위와 같이 행렬곱셈과 동시에 분할정복으로 작은 단위 ~ 큰 단위로 답을 도출해야 한다.

---

🌱 코드 및 풀이

 

만약 size /2 가 짝수라면 그냥 행렬 A * 행렬 A 해서 return 하면 답을 구할 수 있지만  홀수인 경우에는

 

(A^2)^2 * A = A^5

 

위 공식처럼 제곱수가 홀수 일 때는( 행렬^2) * 초기행렬 을 해주면 제곱수가 홀수인 답은 구할 수 있다.

 

코드아래에 반례를 적어놨는데 개인적으로 구현에 신경을 쓴 나머지 경곗값의 예외처리를 신경 쓰지 못했다.

왜맞틀 시 한번 테스트해 보는 것도 좋을 것 같다.

 

---

🌱 느낀 점

B <= 100,000,000,000 이여도 압도적으로 빠르다.

 

다른 분류의 알고리즘을 연습하느라 분할 정복이라는 분야는 자주 접해보지 않았다 그래서인지 분할정복으로 해결해야겠다는

아이디어를 떠올리지 못했다 역시 편식은 안 좋다. 이번 기회에 분할정복, 행렬제곱에 관해 문제를 풀면서

오랜만에 깊게 이해하려고 노력했다 자주 풀어서 까먹지 말아야겠다 ㅠㅠ