axa1239   10달 전

읽어 주셔서 감사합니다

우선 해결 방식으로는 분할 정복으로써 해결 하였습니다. 

두개의 코드 모두 분할 정복 방식이지만 코드를 조금 수정 하여 시간 초과를 피할 수 있었습니다. 

오버라이딩을 통하여 행렬의 곱셈을 정의 하였고 곱한 결과를 반환 하게 구성 하였습니다.

cal 함수 - >  분할 정복 방식으로 행렬의 곱셈을 처리 하였습니다.

밑에  소스 코드와 같이 cal1은 시간 초과를 받은 코드이고 cal2 는 통과한 코드 입니다

도대체 어떤 부분에서 시간이 걸리는지 이해가 가질 않습니다 고수분들 도와주세요!!

herdson   10달 전

4번째 줄에 문제가 있습니다.

왜냐하면 전처리가 안되고 재귀를 돌리므로 결국엔 logn번 제곱하는게 아니라 n번 제곱하는 것과 동일해집니다.

행렬에서 큰 수 제곱을 제대로 구현하기 위해서는 11번째 줄처럼 다음 재귀로 넘어가기전 사전에 n * n의 결과를 계산하고 이를 인자로 넘겨주어야 합니다.

axa1239   10달 전

아.... 꽉 막히던게 이제야 이해가 갑니다 

정말 감사드립니다.

결국에는 return cal(a, m / 2) * cal(a, m / 2)  부분에서

cal 2번 호출이 되어서 n번 제곱하는것 과 같다 이 말씀이신거죠? 

감사합니다!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

herdson   10달 전

네 맞습니다. 잘 이해하셨습니다.

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