분할정복 (Divide and Conquer)
쉽게 풀면
두꺼운 전화번호부에서 특정 이름을 찾는 상황을 떠올려보세요. 첫 페이지부터 한 장씩 넘기며 찾으면 오래 걸리지만, 책을 절반으로 쪼개 찾는 이름이 앞쪽에 있는지 뒤쪽에 있는지 판단한 뒤, 해당하는 절반만 다시 절반으로 쪼개는 식으로 반복하면 훨씬 빨리 찾을 수 있습니다.
이렇게 큰 덩어리를 계속 절반(혹은 여러 조각)으로 나누어 각각을 간단히 해결한 다음, 그 답들을 다시 조립해서 전체 답을 만드는 전략이 분할정복입니다. "나누기(Divide) → 각자 풀기(Conquer) → 합치기(Combine)"의 세 단계로 요약됩니다.
왜 중요한가
분할정복은 정렬, 탐색, 행렬 연산 등 컴퓨터과학의 기초 알고리즘 설계 패러다임 중 하나로, 문제의 규모가 커질수록 계산량이 얼마나 늘어나는지를 분석하는 알고리즘 복잡도 이론과 밀접하게 연결됩니다. 또한 부분 문제들이 서로 독립적이라는 특성 덕분에 병렬·분산 컴퓨팅 환경에 자연스럽게 적용할 수 있어, 대규모 데이터를 다루는 시스템 논문에서 성능 개선 전략으로 자주 인용됩니다.
어떤 절차인가
- 분할: 문제를 같은 종류의 더 작은 문제 a개로 나눕니다(각 크기 약 n/b).
- 정복: 부분 문제를 재귀로 풉니다. 충분히 작아지면(기저 사례) 직접 풉니다.
- 결합: 부분 문제의 답을 합쳐 원래 문제의 답을 만듭니다.
실행 시간은 점화식 T(n) = a·T(n/b) + f(n)으로 씁니다. f(n)은 나누고 합치는 비용입니다. 이 형태의 점화식은 마스터 정리로 풉니다. 병합 정렬은 T(n) = 2T(n/2) + Θ(n)이어서 Θ(n log n), 이진 탐색은 T(n) = T(n/2) + Θ(1)이어서 Θ(log n)입니다.
언제 쓰고 무엇을 얻나
정렬, 탐색, 행렬 곱셈, 고속 푸리에 변환처럼 문제를 독립적인 부분으로 나눌 수 있을 때 씁니다. 부분 문제가 서로 독립이라 여러 프로세서에서 병렬로 풀기 좋습니다.
가상의 예(실험) 같은 난수 배열에서 병합 정렬(분할정복)과 삽입 정렬이 한 비교 횟수를 센 결과입니다(시드 고정).
| 입력 크기 n | 병합 정렬 | 삽입 정렬 | n·log₂n |
|---|---|---|---|
| 100 | 543 | 2,234 | 664 |
| 1,000 | 8,702 | 251,459 | 9,966 |
| 10,000 | 120,495 | 24,788,345 | 132,877 |
n이 100배 커질 때 병합 정렬의 비교 횟수는 약 220배, 삽입 정렬은 약 1만 1천 배가 됩니다. n·log₂n은 병합 정렬 횟수의 상한 근처에 있는 값입니다.
부분 문제가 서로 겹치면 같은 계산을 반복하므로 동적계획법이 낫습니다. 나누고 합치는 비용이 크면 분할이 이득이 되지 않을 수도 있고, 항상 탐욕 알고리즘보다 빠른 것도 아닙니다.
논문에는 이렇게 적는다
- 분할 방식: 몇 개로, 어떤 기준으로 나누는지와 기저 사례의 크기를 적습니다.
- 결합 비용: 합치는 단계의 비용을 명시하고 점화식과 풀이(마스터 정리 등)를 제시합니다.
- 병렬화: 부분 문제를 장치에 어떻게 나누는지, 통신 비용과 부하 균형을 논합니다.
- 실험: 입력 크기별로 실행 시간이나 연산 횟수를 보고하고 이론 복잡도와 맞는지 확인합니다.
논문에서는 이렇게 쓰입니다
실제 논문에서
이 용어를 직접 쓴 국내 논문 문장을 아직 수집하지 못했습니다. 수집되는 대로 출처와 함께 싣겠습니다.
예시 문장
아래는 용어의 쓰임을 보여 주려고 만든 예시로, 실제 논문에서 가져온 문장이 아닙니다.
이 문장은 하나의 크고 복잡한 작업을 여러 개의 작은 독립적인 작업으로 나누어 동시에 처리한 다음, 그 결과들을 합쳐서 최종 결과를 얻는 방식을 사용했다는 뜻입니다. 정렬 알고리즘, 대규모 데이터 병렬 처리, 신호·이미지 처리 분야에서 계산 효율을 높이기 위해 자주 언급됩니다.
생물정보학 분야에서도 긴 서열 데이터를 작은 구간으로 나누어 각각 분석한 뒤 결과를 통합하는 방식으로 분할정복 전략이 활용된다는 뜻입니다.
최적화 알고리즘 연구에서는 전체 탐색 공간을 반복적으로 절반씩 좁혀나가며 계산 효율을 높이는 데에도 분할정복 개념이 응용된다는 의미입니다.
조금 더 깊게 보면
분할정복 알고리즘의 효율성은 흔히 재귀 관계식(recurrence relation)을 세우고 이를 마스터 정리(Master Theorem) 같은 방법으로 분석해 시간 복잡도를 도출합니다.
나누는 단계와 합치는 단계에 드는 비용, 그리고 나뉜 부분 문제의 개수와 크기가 전체 성능을 좌우하며, 이 균형이 깨지면 오히려 비효율적인 경우도 있습니다. 병렬 컴퓨팅 맥락에서는 부분 문제들을 여러 프로세서나 노드에 분배하는 과정에서 통신 비용과 부하 분산(load balancing)이 추가로 고려해야 할 요소가 됩니다.
주의할 점
분할정복은 부분 문제들이 서로 겹치지 않고 독립적일 때 가장 효과적입니다. 만약 나뉜 부분 문제들이 같은 계산을 반복해서 포함한다면, 그 결과를 저장해두고 재사용하는 동적계획법을 쓰는 편이 더 효율적일 수 있습니다. 또한 문제를 나누고 합치는 과정 자체에도 비용이 들기 때문에, 항상 탐욕 알고리즘보다 빠른 것은 아닙니다.
헷갈리기 쉬운 용어
| 기법 | 문제를 어떻게 푸나 | 적합한 경우 |
|---|---|---|
| 분할정복 | 독립적인 부분 문제로 나눠 각각 풀고 합침 | 부분 문제가 겹치지 않을 때 |
| 동적계획법 | 부분 문제의 답을 저장해 재사용 | 부분 문제가 겹칠 때 |
| 탐욕 알고리즘 | 매 단계 지금 가장 좋은 선택을 반복 | 국소 최선이 전체 최선이 되는 구조일 때 |
| 마스터 정리 | 분할정복 점화식의 복잡도를 구하는 공식 | 분석 도구 |
참고 문헌
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
- Knuth, D. E. (1998). The Art of Computer Programming, Volume 3: Sorting and Searching (2nd ed.). Addison-Wesley.
- Bentley, J. L., Haken, D., & Saxe, J. B. (1980). A general method for solving divide-and-conquer recurrences. ACM SIGACT News, 12(3), 36–44.
표의 기준값은 위 문헌에 근거한 관례이며, 분야·학술지마다 다른 기준을 쓸 수 있습니다.