(알고리즘) Divide and Conquer (분할 정복) 전략

Divide and Conquer (분할 정복) 전략

개념 정리

**Divide and Conquer(분할 정복)**는 컴퓨터 과학에서 널리 사용되는 문제 해결 전략 중 하나로, 다음 세 단계로 이루어져 있습니다:

1. Divide (분할)
   • 주어진 문제를 **더 작고 유사한 하위 문제들(sub-problems)**로 나눈다.
   • 각 서브 문제는 원래 문제와 구조적으로 유사하며, 전체 문제를 분해하여 해결 가능하도록 만든다.
2. Conquer (정복)
   • 나눠진 서브 문제들을 재귀적으로 해결한다.
   • 더 이상 나눌 수 없을 정도로 작은 문제(기저 조건 base case)는 직접 해결한다.
3. Combine (통합)
   • 해결된 서브 문제들의 결과를 합쳐서 전체 문제의 해답을 구성한다.

주요 특징

• 재귀 호출을 기반으로 하며, 하향식(top-down) 방식의 문제 해결 접근을 사용한다.
• 일반적으로 시간 복잡도 개선에 유리한 구조를 가진다.
• 하위 문제 간의 중복이 없고 독립적인 경우 가장 효과적이다.

사진 출처 - 유튜브 쉬운코드

---

대표 활용 예시

• Merge Sort (병합 정렬)
• Quick Sort (퀵 정렬)
• Binary Search (이진 탐색)
• Closest Pair Problem
• Strassen’s Matrix Multiplication
• FFT(Fast Fourier Transform)

---

Merge Sort (병합 정렬)

개요

Merge Sort는 Divide and Conquer 전략을 대표적으로 사용하는 정렬 알고리즘으로, 다음과 같은 과정으로 작동합니다:

1. Divide (분할)

• 배열을 절반으로 분할한다.
• 이 과정을 재귀적으로 반복하여, 원소가 하나일 때까지 나눈다.

2. Conquer (정복)

• 각각의 **작은 배열(길이 1)**은 이미 정렬된 상태로 간주한다.

3. Combine (병합)

• 분할된 배열들을 두 개씩 병합하며 정렬한다.
• 정렬된 두 배열을 비교하며, 작은 값부터 하나씩 새로운 배열에 넣는다.
• 병합 과정은 원소 개수만큼의 비교 연산이 필요하다.

예시

[8, 3, 5, 4, 7, 6, 1, 2]

→ Divide
[8, 3, 5, 4]   [7, 6, 1, 2]
[8, 3] [5, 4]   [7, 6] [1, 2]
[8] [3] [5] [4]   [7] [6] [1] [2]

→ Conquer (base case)
각 원소는 이미 정렬되어 있음

→ Combine (merge)
[3, 8] [4, 5]   [6, 7] [1, 2]
[3, 4, 5, 8]     [1, 2, 6, 7]
→ [1, 2, 3, 4, 5, 6, 7, 8]

사진출처 - 유튜브 쉬운코드

 

 

 

* Merge Sort는 배열을 재귀적으로 잘게 나눈 뒤, 정렬된 상태로 병합하면서 다시 재귀적으로 위로 올라간다.

 

 

 

 

 

코드로 보는 merge sort

사진 출처 - 유튜브 쉬운코드

 

시간 복잡도 분석

 

단계	복잡도
분할	O(log n) → 배열을 반으로 나누는 횟수
병합	O(n) → 각 단계에서 전체 배열을 순회
총합	O(n log n)

 

• 공간 복잡도는 보조 배열을 사용하므로 O(n)

---

왜 Merge 단계가 마지막에 필요한가?

많은 사람들이 궁금해하는 포인트는 다음입니다:
“정렬이 된 배열들끼리 합치는데 왜 또 다시 비교해서 새로운 배열에 넣는가?”

→ 그 이유는 정렬된 배열을 유지하며 합치기 위해서입니다.
단순히 배열을 이어붙이면 정렬이 깨지기 때문에, 두 배열의 앞쪽 요소부터 비교해서 작은 값부터 넣는 방식으로 정렬 상태를 유지하는 것입니다.

즉, 병합(merge) 과정은 단순한 배열 복사가 아니라 정렬된 병합입니다.

---

기타 정리

• Stable Sort: 원래의 순서를 유지한다. (ex. 값이 같으면 기존 순서를 보장)
• Recursive Approach를 활용하므로, 함수 호출 스택도 고려해야 한다.
• 정렬 외에도 병합 기반 로직이 필요한 문제(예: 투포인터, K-way merge)에도 사용된다.

---

마무리 요약

• Divide and Conquer는 복잡한 문제를 단순한 하위 문제로 분해하고, 재귀적으로 해결한 뒤 합쳐서 최종 해결하는 전략.
• Merge Sort는 이 전략을 정렬에 최적화된 형태로 구현한 알고리즘이다.
• 시간 복잡도 O(n log n)으로, 정확하고 안정적인 정렬 알고리즘으로 널리 사용된다.