분할 정복 알고리즘

1805년 12월 2일 아우스터리츠 전투에서 나폴레옹이 사용한 전략

중앙부로 쳐들어가 연합군을 둘로 나우어
한 부분씩 격파함

설계 전략

분할 : 해결할 문제를 여러 개의 작은 부분으로 나눈다.
정복 : 나눈 작은 문제를 각각 해결한다.
통합 : 해결된 해답을 모은다.

거듭 제곱(Exponentiation)

분할 정복 기반의 알고리즘 : O(log2n)

C**n  = C**n/2 * C**n/2          n은 짝수
	  = C**n-1/2 * C**n-1/2 * C  n은 홀수

퀵 정렬

주어진 배열을 두 개로 분할하고 각각을 정렬한다.
분할할 때 기준 아이템 (pivot item) 중심으로 작은 것을 왼편으로 큰 것을 오른편에 위치
정렬 후 후처리 작업이 필요가 없다