astrohsy   1년 전

b가 매우 커질 때, 무식하게 다 따라가가지고 시간초과 나는 것은 알겠는데..

그 방법 말고, 어떻게 접근할 수 있지는지 힌트 좀 부탁드립니다. ㅠㅠ

kesakiyo   1년 전

Square and Multiply 를 사용하면 매우 큰 수의 거듭제곱에 대해서 효율적으로 계산할 수 있습니다.

예를 들어 a^10 이라는 수가 있다고 가정해보져

그러면 보통 a*a*a*a*a*a*a*a*a*a 이렇게 계산을 하는데 n이 작으면 잘 동작하겠지만

n이 막 10억 100억 이러면 시간내에 들어올 수가 없죠.

그러면 a^10을 조금 바꿔볼께요. 10을 2진수로 표현을 하게되면 1010(2) 가 나오게 됩니다.

이걸 이용해서 a^10을 다시 표현을 해 볼게요

a^2 * a^8 = a^10 이라는 결과를 도출할 수 있고

결과적으로 a^1, a^2, a^4, a^8 ..... 을 이용해서 모든 a^n 을 빠르게 계산할 수 있습니다.

시간복잡도는 O(n) 에서 O(logn) 으로 줄어들게 되고요.

뭔가 빠르게 넘어간거 같지만 잘 생각해보면 알 수 있을꺼에요!!


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