거듭제곱 (1) 썸네일형 리스트형 백준 1629 - 곱셈 www.acmicpc.net/problem/1629 $A^{B} \mod C$ 를 빠르게 구해야 하는 문제이다. 단순하게 반복문을 통해 구한다고 하면 최대 2,147,483,647번 연산해야 하므로 이는 시간 내로 해결이 불가능하다. 따라서 해결을 위해서는 다른 방법이 필요하다. 이 문제 해결에 사용되는 알고리즘은 PS를 하는데 기본 소양이 되므로 그 방법을 잘 익히도록 한다. 예시로 $2^{1024}$를 구한다고 가정해보자. $2^{1024}$는 $2^{1024} = 4^{512}$ 으로 나타낼 수 있다. 그러면 $4^{512}$도 $4^{512} = 8^{256}$ 으로 나타낼 수 있다. 이처럼 지수를 절반씩 쪼개가며 제곱하면 $O(\log n)$의 시간복잡도로 빠르게 계산할 수 있다. 지수를 절반으.. 이전 1 다음
