크고 다루기 힘든 문제를 같은 모양의 작은 문제로 쪼개 각각 푼 뒤, 그 답들을 합쳐 원래 문제의 답을 만드는 전략. 알고리즘 하나가 아니라 여러 알고리즘의 뼈대가 되는 문제 해결 방식이다.
분할, 정복, 조합
세 단계로 돈다. 분할(divide)은 문제를 작은 크기의 부분 문제로 나눈다. 정복(conquer)은 부분 문제를 같은 방식으로 재귀적으로 풀되, 더 나눌 수 없으면 직접 푼다. 조합(combine)은 부분 문제의 답을 합쳐 원래 문제의 답을 만든다.
더 나눌 수 없으면 직접 푼다는 것이 재귀의 종료 조건이다. 합병 정렬에서는 원소가 하나 남았을 때가 그 지점이고, 원소 하나는 이미 정렬된 상태라 아무것도 안 해도 된다.
깊이가 log n이 되는 것
빨라지는 이유는 깊이에 있다. n개짜리 문제를 반씩 나누면 깊이가 log n이 되고, 각 깊이에서 전체 n개를 한 번씩 처리하면 n log n이다. O(n²)짜리 단순한 방법을 O(n log n)으로 끌어내리는 것이 대부분 이 구조다. 물론 나눈 결과를 합치는 비용이 싸야 성립한다. 합치는 데 O(n²)이 든다면 나누는 의미가 없다.
이 뼈대를 쓰는 알고리즘
합병 정렬이 분할 정복을 이해하기 가장 좋은 예다. 정확히 반씩 나누고, 정렬된 두 조각을 합친다.
퀵 정렬은 피벗을 기준으로 나눈다. 균등하게 나뉘지 않는다는 점이 합병 정렬과 다르고, 그래서 최악이 O(n²)이다.
이분 탐색은 나눈 뒤 한쪽만 보므로 조합 단계가 없다. 가장 단순한 형태다.