1. 분할정복 (Divide and conquer)

1. 사용법

주어진 문제를 둘 이상의 부분 문제로 나눈 뒤  각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산할 수 있을 때 사용한다.

 

2. 구성요소

Divide: 커다란 상황을 작은 상황으로 구획한다.

Conquer: 작은 상황에서의 정답을 토대로 커다란 상황에서의 답을 도출한다.

Base case: 가장 기본적인 상황 (더이상 작은 상황으로 구획할 수 없는 경우를 설정해야 한다.)

 

3. 조건

문제를 부분 문제로 나눠 풀기가 수월해야 한다.

부분문제들의 답을 토대로 원래 문제의 답을 쉽게 도출할 수 있어야 한다.

 

4. 예시

 

1) 백준 1629번 곱셈 (거듭제곱에서의 활용)

 

만약 단순하게 A를 B번 곱하고 이를 C로 나누어 나머지를 구하는 방식으로 이 문제를 풀게될 경우, 각 숫자들이 매우 큰 경우에는 시간안에 구할 수 없다.

따라서 수학적으로 접근하여 최대한 단순화 시켜야 한다.

 

나머지공식을 활용하여 다음 조건을 다른 관점에서 접근하면 다음과 같다.

 

만약 A가 k*C + m (단, k와 m은 자연수)라고 하면 k는 몫, m은 나머지이다.

이때 A에 A를 곱하게 되면 (k * c + m) * (k * c + m)이 되는데 

위의 식을 c에 대해 정리하게 되면 결과적으로 m * m에 의해 나머지가 결정된다는 것을 쉽게 알 수 있다.

 

즉, A를 여러번 연산하는 상황에서 C를 기준으로 했을때의 나머지는 각 상황에서의 나머지끼리의 연산의 나머지와 동치이다.

 

여기까지 분석하였으면, 그 다음부터는 분할정복을 통해 분석해주면 된다.

 

예를 들어 A의 8승의 경우는,  (((A**2)**2)**2)의 방식으로 총 연산을 3번만 해주면 된다.

이와 비슷하게 A가 홀수이면 하나를 빼고 짝수와 동일하게 진행해주면 된다.

그러면 필요한 계산이 압도적으로 줄어서 빠른 시간안에 문제를 해결할 수 있게 된다.

import sys

A, B, C = map(int, sys.stdin.readline().split())

remain_first = A % C

# A ** n = A ** (n - 1) * A = (C * n + remain1) * (C + m + remain2)
# So, the result is same as calcaulte remainder (By using divide and conquer)

def multiplier(remain, above):
    if above == 1:
        return remain
          
    if above % 2 == 0:
        return (multiplier(remain, above // 2) ** 2) % C

    else:
        return (multiplier(remain, above // 2) ** 2 * multiplier(remain, 1)) % C

# Print result

print(multiplier(remain_first, B))

위의 알고리즘을 바탕으로 문제를 풀어보면 다음과 같다.

이 문제를 풀기위하여 걸리는 시간은 above를 n이라 할 때, O(log2(n))임이 알려져 있는데

B의 범위를 보았을 때, 시간안에 풀 수 있음을 알 수 있다.

 

 

이 문제 외에도 병합 정렬(Merge sort) 등이 분할 정복 알고리즘을 사용하는 대표적인 예시라고 할 수 있다.