분할 정복 알고리즘 python

원리

문제를 부분문제로 분할하고, 분할된 문제들을 해결후에 다시 조합해나가서 결과를 도출하는 알고리즘

 

https://namu.wiki/w/%EB%B6%84%ED%95%A0%20%EC%A0%95%EB%B3%B5%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

분할 정복 알고리즘 - 나무위키

 

 

 

 

 

예시

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

위 문제를 풀려고 A**B%C라고 작성하면 시간초과가 뜬다.

왜냐하면 A**B는 A를 B번 곱하기 때문에 시간복잡도가 O(N)이 된다.

이를 해결하기 위해 2가지 법칙을 사용해야한다.

지수법칙

 

나머지 분배법칙

(A + B) % C = ((A % C) + (B % C)) % C (A * B) % C = ((A % C) * (B % C)) % C (A - B) % C = ((A % C) - (B % C) + C) % C

나머지 분배법칙을 이용해서 위 문제를 분할 정복 알고리즘을 적용할 수 있다.

 

 

나머지 분배법칙으로 입력 예시의 10 11 12를 풀자면,

10**11%12 = ((10**5%12) * (10**5%12)) % 12

이렇게 쪼갤 수 있다.

10**5또한 (10**2)*(10**2)*10으로 쪼개고 10**2또한 쪼개고 나면 가장 작은 부분문제가 완성된다.

이를 해결한 후 다시 합하면 원래의 답을 찾을 수 있게된다.

시간복잡도는 트리형태로 풀었기 때문에 O(logN)이 된다.

 

 

이를 코드로 작성하면

def sol(A, B, C):
    if B==1:
        return A%C
    res = sol(A, B//2, C)
    if B%2:
        return (res*res*A)%C
    else:
        return (res*res)%C

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

 

 

이렇게 적을 수 있다.

 

sol(A, B//2, C)를 계속 반복하기 때문에 res로 묶었다.

 

 

 

 

 

 

참조

https://hbj0209.tistory.com/43

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