알고리즘 문제 해결 전략 - 7장 분할 정복(Divide & Conquer)

분할 정복(Divide & Conquer)

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

※ 분할 정복이 일반적인 재귀 호출과 다른 점은 문제를 한 조각과 나머지 전체로 나누는 대신 거의 같은 크기의 부분 문제로 나누는 것입니다.

※ 분할 정복은 많은 경우 같은 작업을 더 빠르게 처리해 줍니다.

1. 분할 정복을 사용하는 알고리즘 세 가지의 구성 요소

- 문제를 더 작은 문제로 분할하는 과정(divide)

- 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정(merge)

- 더이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제(base case)

ex1) 1부터 n까지의 합 속도 비교 (일반적인 재귀 호출 vs 분할 정복 vs 반복문)

if) n==1000

reference) 프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략