분할 정복: 백준 1629번 오답노트

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

1. 개요

• 문제 정의:
  자연수 ( A, B, C )가 주어졌을 때, ( $A^B$ )를 구한 후 ( C )로 나눈 나머지, 즉 ( $A^B \mod C$ )를 계산.
• 문제점:
  ( B )가 매우 크면 ( A )를 ( B )번 곱하는 직접적인 방법은 연산 횟수가 많아 비효율적.
• 해결책:
  분할 정복(Exponentiation by Squaring) 기법을 사용하면 곱셈 횟수를 ( $O(B)$ )에서 ( $O(\log B)$ )로 줄일 수 있음.

---

2. 기초 수학 이론

• 거듭제곱의 기본 정의:
  $A^B = \underbrace{A \times A \times \cdots \times A}_{B \text{번 곱함}}$
• 분할 정복의 핵심 원리:
  • 짝수 지수:
    $A^B = \left( A^{B/2} \right)^2$
    예: ( A^8 = (A^4)^2 )
  • 홀수 지수:
    $A^B = A^{B-1} \times A$
    예: ( A^9 = A^8 \times A )
• 모듈러 연산의 성질:
  $(X \times Y) \mod C = \left[ (X \mod C) \times (Y \mod C) \right] \mod C$
  → 연산 중간마다 모듈러 연산을 적용해 값의 크기를 관리할 수 있음.

---

3. 분할 정복 거듭제곱 알고리즘의 동작 원리

• 재귀 호출 구조:
  1. 기저 조건:
     ( $B = 1$ )이면 ( $A \mod C$ )를 반환.
  2. 재귀 호출:
     ( B )를 절반으로 나누어 ( $A^{B//2} \mod C$ )를 구함.
  3. 짝수/홀수 분기 처리:
     • B가 짝수인 경우:
       $(A^B) \mod C = (A^{B//2} \mod C)^2 \mod C$
     • B가 홀수인 경우:
       $(A^B) \mod C = \left[(A^{B//2} \mod C)^2 \times A\right] \mod C$
• 효율성:
  매 단계마다 지수가 절반으로 줄어들기 때문에 전체 연산 횟수가 ( $O(\log B)$ )에 비례.

---

4. 코드 구현 (재귀 방식)

import sys

def power_mod(A:int, B:int, C:int):
    
    # B가 1인 경우에 재귀 멈추고 거꾸로 타고 올라가며 연산 시작
    if B == 1:
        return A % C
    
    # 모듈러 연산 적용
    # 최종적으로 어떻게든 B가 1이 되고, 그때 A % C 에서부터 타고 위로 올라가며 계산됨.
    # half에 해당 A % C가 담기면 실질적으로 A^2 % C = ((A % C) ^ 2) % C 가 적용되며
    # 모듈러 연산이 이하 식을 통해 이루어 짐.
    partial_result = power_mod(A, B//2, C)
    squared_result = (partial_result*partial_result) % C
    
    # 다만, B // 2 를 통하여 현재 '몫'에 해당하는 값만 쓰고 있는바(소숫점 이하 버림)
    # B가 홀수인 경우에 아래에서 타고 올라오면서 1만큼씩 비므로 아래 처럼 보완
    if B % 2 !=0:
        return (squared_result * A) % C
    
    else:
        return squared_result


def main():
    A, B, C = map(int, sys.stdin.readline().rstrip().split())
    
    print(power_mod(A, B, C))


if __name__ == "__main__":
    main()

• 코드 설명:
  1. ($B = 1$ )이면 ( $A \mod C$ )를 반환.
  2. 재귀 호출로 ( $B//2$ )의 지수에 대해 계산한 후 그 결과를 제곱.
  3. ( $B$ )가 홀수이면, 추가적으로 ( $A$ )를 한 번 곱하여 최종 결과 도출.

5. 실행 예시: ( A=10, B=11, C=12 )

• 재귀 방식 단계별 진행:
  1. power_mod(10, 11, 12) → ( B=11 ) (홀수)
     → 내부 호출: power_mod(10, 5, 12) 후 결과에 ( A ) 곱함.
  2. power_mod(10, 5, 12) → ( B=5 ) (홀수)
     → 내부 호출: power_mod(10, 2, 12) 후 결과에 ( A ) 곱함.
  3. power_mod(10, 2, 12) → ( B=2 ) (짝수)
     → 내부 호출: power_mod(10, 1, 12) 후 결과 제곱.
  4. power_mod(10, 1, 12) → 기저 조건 도달, ( $10 \mod 12 = 10$ ) 반환.
  5. 거꾸로 올라오며 계산:
     $power\_mod(10, 2, 12) = (10 \times 10) \mod 12 = 100 \mod 12 = 4$
     $power\_mod(10, 5, 12) = ((4 \times 4) \mod 12 \times 10) \mod 12 = (16 \mod 12 \times 10) \mod 12 = (4 \times 10) \mod 12 = 40 \mod 12 = 4$
     $power\_mod(10, 11, 12) = ((4 \times 4) \mod 12 \times 10) \mod 12 = 4$
• 최종 결과:
  $10^{11} \mod 12 = 4$