백준 1629번: 곱셈

거듭제곱과 분할 정복 알고리즘

이 문제는 거듭제곱을 효율적으로 계산하기 위한 분할 정복 알고리즘을 사용하는 문제입니다. 거듭제곱 계산은 A의 B승 같은 큰 수를 다루기 때문에, 이를 단순히 반복 계산하면 비효율적입니다. 따라서 분할 정복을 활용하여 계산을 최적화합니다.

 

분할 정복 알고리즘이란?

분할 정복은 문제를 작은 하위 문제로 나누고, 이를 재귀적으로 해결하여 결론을 도출하는 알고리즘입니다. 큰 문제를 나눔으로써 계산량을 줄이고 효율적으로 문제를 해결할 수 있습니다.

분할 정복과 다이나믹 프로그래밍(DP)은 비슷하게 보일 수 있으나, 두 알고리즘은 차이가 있습니다.

 

분할 정복과 DP의 차이

특징	분할 정복	다이나믹 프로그래밍
문제 나누기	문제를 작은 하위 문제로 나눔	하위 문제를 저장하고 중복된 계산을 제거
중복 계산	중복 계산이 있을 수 있음 (최적화되지 않으면)	동일한 계산을 반복하지 않음 (메모이제이션 활용)
적용 사례	병합 정렬, 퀵 정렬, 거듭제곱 등	피보나치 수열, 최단 경로 문제, 배낭 문제 등

 

분할 정복 알고리즘 적용 이유

거듭제곱 문제에서, 단순히 A^B를 계산하려면 B번의 곱셈이 필요합니다. 하지만 분할 정복을 사용하면 계산량을 크게 줄일 수 있습니다.

예를 들어, 10^11을 계산한다고 가정해봅시다.

1. 일반적인 방법:
   • 10×10×10×…10를 11번 곱합니다. 계산량은 O(B)입니다.
2. 분할 정복 방법:
   • 11을 절반으로 나누어 계산:
     • 11=5×2+1 
     • 10^5×10^5×10
   • 이때, 10^5도 분할하여 계산
     • 5=2×2+1
     • 10^2×10^2×10
   • 결과적으로 계산량은 O(log⁡B)로 줄어듭니다.

알고리즘 설명

분할 정복을 활용한 A^B mod C 계산은 다음과 같이 진행됩니다:

1. B가 짝수일 경우:  A^B mod C  =(A^(B//2)modC)^2 modC
2. B가 홀수일 경우: A^B mod  C=(A^(B−1)mod  C)⋅A mod  C
3. B==0인 경우: A^0 mod  C=1

재귀 함수 흐름

예를 들어, A=10,B=11,C=12A = 10, B = 11, C = 12A=10,B=11,C=12일 때 재귀적으로 계산하는 과정을 살펴봅시다.

1. B=11 (홀수):
   • B//2=5
   • 계산: 10^5×10^5×10 mod  12
2. B=5 (홀수):
   • B//2=2
   • 계산: 10^2×10^2×10 mod  12
3. B=2(짝수):
   • B//2=1
   • 계산: 10^1×10^1 mod  12
4. B=1B = 1B=1 (홀수):
   • B//2=0
   • 계산: 10^0×10 mod  12=1×10 mod 12=10

최종적으로 B=0에서 1을 반환하고, 결과를 재귀적으로 계산하여 최종값을 반환합니다.

 

모듈러 연산의 분배 법칙

분할 정복을 활용하면서 모듈러 연산의 분배 법칙이 중요합니다. 이 법칙은 연산이 커지는 것을 방지하고 효율적으로 나머지를 계산하게 합니다.

분배 법칙

(A⋅B) mod  C=((A mod  C)⋅(B mod  C)) mod  C

예를 들어

• A=10,B=11,C=12일 때:
  1. 10 mod  12=10
  2. 10^2 mod  12=(10×10) mod  12=100 mod  12=4
  3. 10^4 mod  12=(4×4) mod  12=16 mod  12=4

이 과정을 통해 숫자를 줄이고 효율적으로 계산할 수 있습니다.

최종 코드

import sys
input=sys.stdin.readline
def mul(a,b,c):
    #종료조건 b가 0일때
    if b==0:
        return 1
    half=mul(a,b//2,c)
    half=(half*half)%c

    if b%2==1:
        half=(half*a)%c


    return half

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