🚀 Power by Divide and Conquer

intro

🅰️ 분할정복(divide & conquer)은 복잡한 문제를 해결할 수 있는 여러 쉬운 문제들로 쪼개서 해결하는 접근법. 정수의 거듭제곱을 구하는 과정에서 분할정복 기법을 활용해 더 효율적인 시간 내에 진행할 수 있다.

 

'실수 a와 음이 아닌 정수 x에 대해 a^x를 구하는 문제'

① x = 1이면 답은 a로 직접 해결

→ 시간복잡도 O(1)

 

②  x > 1이면 sub-problems로 쪼개기.

🅰️ x가 짝수라면 a^(x/2) x a^(x/2)

🅰️ x가 홀수라면 a^((x-1)/2) x a^ ((x-1)/2) x a

→ 시간복잡도 T(x) = T(x/2) + O(1). 즉 T(x) = O(logx)

example 7^10

🅰️ 예를 들어 7^10을 구하는 문제가 있다고 하자. 두 가지 접근법으로 나누어볼 수 있는데,

 

① 7을 10번 곱하는 연산. 곱셈 횟수 10번 카운트 (7x7x7x7x7x7x7x7x7x7)

② 지수인 10을 밑을 2로 하는 log 연산으로 쪼개어 분할정복을 이용한 거듭제곱으로 구하는 연산

 

→ ①은 시간 초과 / ②는 시간 복잡도 O(log2(지수)) 이므로 지수가 1조를 넘어도 깊이가 40을 넘지 않는다. 즉, 예를 들어 7의 1억승도 쉽게 계산할 수 있다는 뜻

 

→ 7의 10승을 구해보자. 지수인 10은 짝수이므로 7의 5승을 제곱한 것. 따라서 7의 5승을 한 번 구하면 구한 결과를 한 번 더 곱해주기만 하면 된다. 7의 5승을 한 번 더 구할 필요가 없다. 그러면 7의 5승을 구하기 위해 이젠 7의 2승을 구하면 된다. 7의 2승을 구하면 구한 결과를 한 번 더 곱하고 7만 곱해주면 된다. 그 다음 7의 2승을 구하기 위해 7의 1승을 구하면 된다. 7의 1승을 구하면 구한 결과에 한 번 더 곱해주면 된다. 이 때 7의 1승에서 지수가 1이므로 recursion 종료하고 7의 1승 리턴해주면 된다.

 

→ 이렇게 재귀적으로 큰 problem을 지수가 홀수인지 짝수인지에 따라 sub-problem으로 분할하고, 분할된 sub-problem을 해결해나가면서 다시 위로 올라가는(recursion) 'divide & conquer' 유형으로 매우 빠르게 O(logn)) (n은 지수) 시간복잡도로 풀 수 있다.

 

→ 아래 파이썬 코드 참조(a의 b제곱 구하기)

def get_power(a,b):
    if b == 1:
        return a
    
    x = get_power(a,b//2)

    if b % 2 == 0:
        return x * x
    else:
        return x * x * a

+ modulo operation

modulo multiplication property

🅰️ 다만, a의 b제곱 결과가 b가 매우 클 경우, 컴퓨터가 큰 수를 나타내기에 감당하지 못한다. 이 때, modulo 연산, 즉 매우 큰 수로 나눈 나머지를 구하는 문제 유형으로 대부분 출제. 이 때 모듈러 곱셈 연산 성질(modulo multiplication property)을 알아야 한다.

ex) 즉, 10을 3으로 나눈 나머지는 (5를 3으로 나눈 나머지) x (2를 3으로 나눈 나머지)와 동일. 3개 이상의 수를 곱한 결과의 modulo opertation도 동일한 과정으로 진행된다. 30을 7로 나눈 나머지는 예를 들어 (3을 7로 나눈 나머지) x (2를 7로 나눈 나머지) x (5를 7로 나눈 나머지)이다.

modulo addition / subtraction property

🅰️ 모듈로 곱셈 성질에 이어 덧셈 / 뺄셈 성질도 동일하다.

+ 추가로 모듈로 곱셉 역원(modular inverse), 즉 나눗셈 관련 모듈로 성질은 페르마의 소정리와 함께 여러 성질을 결합해서 연산 해야 한다. 별도 포스팅 참조

a^b (mod c)

🅰️ 위 modulo property에 의해 a의 b제곱을 c로 나눈 나머지에 대해 구해보자

def get_power(a,b,c):
    if b == 1:
        return a%c
        
    x = get_power(a,b//2,c)

    if b % 2 == 0:
        return ((x%c) * (x%c)) % c
    else:
        return ((x%c) * (x%c) * (a%c))%c

 

: 위 코드에서 %c(divisor)를 항마다 해주어서 modulo multiplication property에 의해 단순히 곱해주면 된다.

Power by Divide & Conquer exercises

examples

★ <BOJ S1 1629 곱셈> ★

: 위 예제 코드와 그대로 동일. A^B을 C로 나눈 나머지를 분할 정복 기법을 사용해 구하는 문제

 

★ <BOJ S1 11819 The Shortest does not Mean the Simplest> ★

: 위 1629 곱셈 문제와 동일 문제

 

★ <BOJ S3 13171 A> ★

: 분할정복을 이용한 거듭제곱 내용을 문제에서 그대로 설명해줌. 위 코드 그대로 사용해 A^B를 1,000,000,007로 나눈 나머지를 구하는 문제

 

★ <BOJ G5 15717 떡파이어> ★

: 가짓수는 2^(N-1)임을 알고 2^(N-1)을 10^9+7로 나눈 나머지를 구하는 문제