분할 정복(Divide and Conquer)은 알고리즘 설계 기법 중 하나로, 복잡한 문제를 작은 단위로 나누어 해결하는 강력한 패러다임입니다. 병합 정렬(Merge Sort), 퀵 정렬(Quick Sort), 이진 탐색(Binary Search) 등 우리가 자주 사용하는 알고리즘 대부분이 이 기법을 기반으로 동작합니다.
분할 정복의 3단계 구조
분할 정복 알고리즘은 크게 다음 세 가지 단계로 구성됩니다.
1. 분할 (Divide)
주어진 문제를 같은 유형의 더 작은 하위 문제(sub-problem)들로 나누는 단계입니다. 문제의 크기를 줄여 해결 난이도를 낮추는 것이 핵심입니다.
2. 정복 (Conquer)
나누어진 하위 문제들을 재귀적으로(recursively) 해결합니다. 하위 문제가 충분히 작아지면 더 이상 나누지 않고 직접 해결하는 기저 조건(base case)에 도달하게 됩니다.
3. 결합 (Combine)
각 하위 문제의 해답을 합쳐서 원래 문제의 최종 답을 도출합니다. 예를 들어 병합 정렬에서는 정렬된 두 부분 배열을 하나로 병합하는 과정이 여기에 해당합니다.
이 섹션에서 다룰 주요 문제
분할 정복 기법의 실제 활용을 익힐 수 있도록, 다음과 같은 대표적인 알고리즘 문제들을 다룹니다.
- 최근접 점쌍 문제(Closest Pair of Points) — 평면상의 점들 중 가장 가까운 두 점을 효율적으로 찾는 문제
- 2차원 배열에서 피크(Peak) 요소 찾기 — 이웃한 원소보다 큰 값을 O(log n) 시간에 찾는 방법
- 배열의 역전(Inversion) 개수 세기 — 병합 정렬을 변형하여 배열 내 순서가 뒤바뀐 쌍의 개수를 계산하는 문제
- 정렬된 두 배열의 중앙값(Median) 구하기 — 두 개의 정렬된 배열을 병합하지 않고 중앙값을 찾는 최적화 문제
각 문제를 통해 분할 정복의 설계 사고방식과 시간 복잡도 분석 방법을 함께 학습하면, 실전 코딩 테스트와 알고리즘 인터뷰에서 큰 도움이 될 것입니다.