분할정복

[알고리즘] 분할정복 (Divide and Conquer)

분할 정복 분할 정복은 그대로 해결하기 어려운 큰 문제를 작은 문제로 분할하여 해결하는 전략이다. 주어진 문제를 둘 이상의 부분 문제로 나누고 각 문제에 대한 답을 재귀적으로 구한다. 그 후, 부분 문제의 답을 이용해 전체 문제의 답을 계산해낸다. 재귀 호출과 다른 점은 문제를 한조각과 나머지 전체로 나누는 대신, 거의 같은 크기의 부분 문제로 나눈다는 것이다. 분할 정복이 필요한 문제의 예시로, 거듭 제곱을 구하는 알고리즘을 구현하면 다음과 같다. def pow(a, b): res = 1 for i in range(b): res *= a return res 단순 반복 연산으로 시간복잡도가 O(b)인 풀이이다. 분할 정복을 통해 더 빠르게 해결할 수 있다. a, b, c = map(int, input()..