분할 정복 (1) 썸네일형 리스트형 [백준 10830][C++] 행렬 제곱 문제 https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 과정 분할 정복 알고리즘을 적용한다. 행렬 곱 함수를 작성한 뒤, 행렬의 제곱을 기록하며 결과를 이용하도록 구현한다. 예를 들어 A^9를 구한다고 가정했을 때, A^9 = A * (A^4) * (A^4) 형태로 곱이 이루어지며, O(logN)의 시간 복잡도를 가진다. 정답 배열을 초기화할 때는 곱을 해도 원래 형태가 나오도록 단위행렬 형태로 초기화해야 한다. 소스 코드 #include #include.. 이전 1 다음
