코테 공부 (1) 썸네일형 리스트형 재귀에서 함수 호출 비용 https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 이 문제를 풀면서 천억단위의 행렬 제곱을 실행하는 알고리즘을 짜야 했다. 처음에 DP를 생각해서 작성하였는데 시간초과가 떴다. 그 후 다른 풀이가 생각나지 않아 결국 검색하여 A^5 = (A^2)^2 * A 와 같이 행렬의 제곱을 부분적으로 나눠서 계산하는 분할정복 알고리즘으로 해결하였다. 그런데 나중에 테스트 해보니 기존의 DP를 활용한 알고리즘과 분할정복을 사용한 알고리즘끼리 10억 단위의 테스트에도 배열 .. 이전 1 다음
