분할정복을 이용한 거듭제곱 빠르게하기

1. 분할정복

 

문제를 더 이상 나눌 수 없을 때까지 더 작은 문제로 나누면서 이 작은 문제들을 각각 풀면서, 병합하여 전체 문제의 답을 구하는 알고리즘

 

divide - conquer - combine 방식으로 설계한다.

 

문제가 분할이 가능하면 2개 이상의 작은 문제로 나눈다(divide)

 

나누어진 문제가 분할이 가능하면, 또 다시 문제를 분할하고 그렇지 않으면 문제를 푼다(conquer)

 

푼 문제들을 통합하여 전체 문제의 답을 구한다(combine)

 

당연하지만 divide를 잘 하면 나누어진 문제를 푸는 것은 매우 쉬우므로 divide를 잘 하는 것이 중요하다

 

재귀알고리즘을 많이 사용하게 되는데, 이 때문에 오히려 효율적이지 못할 수 있다.

 

 

2. 응용 - 거듭제곱

 

n번의 거듭제곱은 자신을 n번 곱하므로 보통 $O(n)$ 시간이 소요된다.

 

예를 들어 $p^8$을 구하는 방법을 생각해보자.

 

이는 p를 8번 곱할 수 있는데, 다르게 생각한다면...

 

$$p^8 = p^4 * p^4 = (p^4)^2 = ((p^2)^2)^2

 

이므로 p^2을 3번 반복하면 8번 반복할 것을 3번만에 구할 수 있다.

 

만약 지수가 짝수이면, 그냥 지수를 반으로 나눠서 곱하고

 

지수가 홀수이면 1을 하나 뺀 뒤에 나머지 지수를 반으로 나눠서 곱하면 된다

 

 

이렇게 계산하면 $O(logn)$만에 거듭제곱을 수행할 수 있다.

 

하지만 n이 정수여야함

 

 

3. 예시 코드

 

3-1) 재귀함수 이용

 

반복문보다 살짝 느릴 수 있고 재귀 깊이가 깊어지면 에러가 날 수 있다

 

def power(a:float, n:int):
    
    if n == 0:
        
        return 1
    
    else:
        
        x = power(a,n//2)
        
        if n % 2 == 0:
            
            return x*x
        
        else:
            
            return x*x*a

 

3-2) 반복문 이용

 

def power(a:float, n:int):
    
    result = 1
    
    while n:
        
        if n % 2 == 1:
            
            result *= a
        
        a *= a
        
        n = n//2
    
    return result

 

혹은 조금 더 어렵게 비트연산을 활용하면, n&1은 n의 1의 자리 비트가 1이면 1이고 0이면 0을 나타내는 것으로

 

짝수이면 1의 자리 비트가 0이고 홀수이면 1의 자리 비트가 1

 

그래서 홀수이면 True이고 짝수이면 False가 된다

 

또한 n >> 1은 n을 한비트 오른쪽으로 옮기는 것으로 1/2배가 된다

 

def power(a:float, n:int):
    
    result = 1
    
    while n:
        
        if n&1:
            
            result *= a
        
        a *= a
        
        n = n>>1
    
    return result

 

3-3) 파이썬의 함수 이용

 

pow() 함수가 거듭제곱 연산을 제공하고, 3번째 인자로 mod연산까지 제공함

 

 

거듭제곱 연산자를 사용한 것과 동일하다는 것으로 보아서... 애초에 파이썬은 연산자가 분할정복으로 계산하나봐

 

 

4. 예시 문제

 

매우 큰 수의 거듭제곱을 어떤 수로 나눈 나머지를 구하는 문제

 

https://www.acmicpc.net/problem/1629

1629번: 곱셈

 

여기서 또 하나 알아야할 점은 나머지 연산의 또 하나의 성질

 

 

4-1) mod 연산의 거듭제곱

 

만약 a와 b가 p로 나눈 나머지가 서로 동일하다면, $a^k$와 $b^k$을 p로 나눈 나머지도 서로 동일하다

 

 

 

만약 11을 10으로 나눈 나머지는 1이므로, 11과 1은 mod 10에 대해 합동이다.

 

 

그래서 11^(1000)을 10으로 나눈 나머지는 , 1^(1000)을 10으로 나눈 나머지와 같다

 

from sys import stdin

def power(a,n):
    
    result = 1
    
    while n:
        
        if n % 2 == 1:
            
            result *= a
        
        a *= a
        a = a%c
        n = n//2
    
    return result

a,b,c = map(int,stdin.readline().split())

print(power(a,b)%c)

 

분할정복을 이용한 거듭제곱으로 a^b를 구하는데, 모듈러 연산의 거듭제곱 성질을 이용해서

 

a를 제곱할때마다, 제곱한 수를 c로 나눠주면, 여전히 나머지는 동일하다는 것이다.

 

그러면 시간을 더 줄일 수 있다

 

 

그러면 홀수일때, a 하나씩만 곱해지는 경우도 있지 않냐?

 

합동식의 양변에 동일한 수를 곱해도 나머지는 변하지 않는다

 

 

당연하지만 c와 c는 m에 대해 당연히 합동이므로, a와 b가 m에 대해 합도이면 ac와 bc도 합동이다

 

그래서 거듭제곱 과정에서, 계속 c를 나눠줘도 전체 결과에서 c를 나눈 나머지는 변하지 않는다

 

수를 계속 줄여주면서 곱하는 과정에서 시간을 줄이게 된다

 

 

5. 참조

 

https://janghw.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Divide-and-Conquer-%EB%B6%84%ED%95%A0%EC%A0%95%EB%B3%B5

[알고리즘] Divide and Conquer (분할정복)

 

https://hbj0209.tistory.com/43

[Algorithm] 분할정복을 이용한 거듭제곱

 

https://sskl660.tistory.com/75

모듈러 산술(Modular Arithmetic)