분할 정복

p. 175 ~ p. 205

분할 정복

1. 주어진 문제를 둘 이상의 부분문제로 나눈 뒤, (Divide)
2. 각 문제의 답을 재귀호출을 통해 계산 후 (Merge)
3. 각 답으로부터 원래 문제의 답을 계산하는 알고리즘 (Base case)

순수 재귀호출 방식과 다른 점

재귀호출	분할 정복
1 문제 + 나머지 (재귀호출)	부분문제 (재귀호출) + 부분문제 (재귀호출)
1 ~ N 합
N 번의 호출	lgN 번의 호출
sum(n-1) + n	2 * sum(n / 2) + (n / 2) * (n / 2)  (if, n 짝수)  sum(n - 1) + n                         (if, n 홀수)

병합 정렬과 퀵 정렬

병합 정렬 (Merge Sort)	퀵 정렬 (Quick Sort)
O(nlgn)	O(nlgn)
병합 단계에서 연산 수행	분할 단계에서 연산 수행
	pivot 잘못 선택 시 최악의 경우 O(n²) 이 될 수 있음

문제

쿼드 트리 뒤집기

울타리 잘라내기