알고리즘/백준(BOJ)
[백준/C++] 10830번 행렬 제곱
https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 얼핏보면 그냥 행렬 곱을 반복해주면 되는거 아닌가? 싶을 수도 있다. 하지만! 최대 천억제곱까지 주어지므로 O(N)에는 해결할 수 없다! 때문에 빠른 거듭제곱 알고리즘을 사용해야한다. 즉, N이 홀수일 땐 밑을 하나 꺼내서 N을 짝수로 만든다. N이 짝수일 땐 밑을 제곱하고 N을 2로 나눈다. 그럼 어떻게 이 문제를 풀어야할까? 우선 행렬곱을 해주는 함수를 하나 만든다. 배열을 파라미터로 넘길 땐 주소가 넘..
