[Algorithm] 거듭제곱을 이진수를 이용하여 해결하기

만약 우리가 A라는 정수를 13번 곱해야한다고 가정하자
그럼 A^13이 될 것이다.

이것을 for문, while문을 이용한 단순한 반복문을 사용하여 해결한다면 엄청난 시간이 소요될 것이다.

이진수를 이용하여 이를 해결할 수 있다.

이진수 사용 원리

0010(2)을 제곱하면 0100(2)이 되고 0100(2)을 제곱하면 1000(2)이 된다.

또한 1101(2)에서 2를 나눈 나머지를 살펴보면,

1. 1101(2) / 2 = 110(2)...1
2. 110(2) / 2 = 11(2)...0
3. 11(2) / 2 = 1(2)...1
4. 1(2) / 2 = 0...1

나머지를 이용하여 기존의 이진수를 구할 수 있다는 것을 알 수 있다

이제 이 원리들을 사용하여 거듭제곱을 구해볼 것이다.

코드

def answer(a, b):
    ret = 1
    while b:
        if b % 2 == 1:
            ret = ret * a
        a =  a * a
        b //= 2

    return ret

a,b,c = map(int ,input().split())
print(answer(a, b))

지수를 계속해서 2로 나누어 나머지를 구한다.
나머지가 1이라면 그 부분은 곱해져야 하므로 a를 곱한다.
a는 반복을 거칠 때마다 제곱 연산을 거치고 지수인 b는 반복을 거칠 때마다 2로 나뉜다