hwpark12   2년 전

분할 정복을 이용해 행렬의 제곱을 구하려고 했는데 시간초과가 나네요...

u는 n*n 크기의 단위행렬을 구한 것이고,

prod 함수는 두 행렬 m1, m2를 곱해주는 함수이고

exp 함수는 행렬 m의 b제곱을 분할 정복을 이용해 구해주는 함수입니다.

도와주세요 ㅠㅠ

woosukji   2년 전

메모이제이션을 안하시면, 아무리 재귀로 분할 정복을 해도 선형 오퍼레이션과 비슷하거나 나쁜 퍼포먼스가 나옵니다.

그런데 일반적인 메모이제이션을 사용해도, B값이 10^11까지 가능한데 그 사이 중간값마다 행렬 결괏값을 저장하면 메모리 초과가 뜰 것 같아요.

많이 쓰시는 풀이를 응용해서, (B 이하 가장 큰 2의 제곱수)를 기준으로 메모이제이션을 쓰는 것도 방법이겠죠.

댓글을 작성하려면 로그인해야 합니다.