[파이썬 알고리즘] 분할 정복

분할 정복 이란?

어떤 문제를 해결하는 알고리즘에서 원래 문제를 성질이 똑같은 여러 개의 부분 문제로 나누어 해결하여 원래 문제의 해를 구하는 방식.

라고 하는데 말로 설명하면 어렵다. 그래도 최대한 이해하기 쉽게 설명을 진행하겠다.

 

먼저 3을 10번 곱한다면 식으로 

$$ 3*3*3*3*3*3*3*3*3*3 = 3^{10} $$이런식으로 계산을 하게 된다.

이때 분할 정복을 사용하면

$$ 3^{2}*3^{2}*3^{2}*3^{2}*3^{2} $$ 

으로 나누어지고 계산된 값인 9를

$$ 9^{2}*9^{2}*9 $$ 

이어서 또 다시 81을 

$$ 81^{2}*9 $$ 

만 계산하면 끝이난다

총 10번 반복할것은 3번으로 줄인것이다.

 

이처럼 분할 정복을 이용하면 시간을 단축시킬 수 있다.

def Recursive_Power(C,n):
    if n ==1:
        return C
    else:
        y = Recursive_Power(C,n//2)
    if n % 2==0:
        return y*y 
    else:
        return y*y*C

관련된 코딩테스트 문제도 많이 나오고 있으니 잘 기억했다가 사용하면 많은 도움이 될듯하다.

백준에서도 실버 1정도의 꽤 높은 문제로도 나오고 있으니 알고있으면 쉽게 문제를 해결할 수 있다.

 

(문제를 풀다가 알게되면 문제 추가할 예정)

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

소프티어 바이러스 : https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=407