[알고리즘] Divide and Conquer(분할정복)이란? | Merge Sort(병합정렬)

정의

Divide and Conquer(분할정복)은 해결하기 힘든 큰 문제를 작은 문제로 분할하여 해결(정복)한 후 병합하는 알고리즘이다.

 

접근법 

분할정복은 보통 다음과 같은 3단계의 과정을 거친다. 

 

1. Divide(분할) : 문제를 더 작은 문제들로 분할 

2. Conquer(정복) : 분할한 작은 문제들을 해결한다. 

3. Combine(병합) : 작은 문제들의 해결법을 병합해 큰 문제의 해결법을 찾는다.  

 

특징

1. 문제를 나눌 때 보통 재귀(recursion)를 많이 사용한다.

2. 재귀(recursion)를 이용할 때 오버헤드가 커 메모리를 많이 사용할 수 있다. 

---

예시

Merge Sort(병합 정렬)

병합 정렬은 분할정복의 대표적인 예이다. n개의 데이터를 가진 배열을 오름차순으로 정렬하기 위해 병합정렬을 사용한다면 아래와 같은 3단계의 과정을 거치게 된다. 

 

1. Divide(분할) : n개의 원소를 갖는 배열을 n/2 개의 원소를 갖는 작은배열 2개로 나눈다.

2. Conquer(정복) : 각각의 작은 배열들을 정렬한다. 

3. Combine(병합) : 정렬된 작은 배열들을 병합한다. 

 

예를 들어 다음과 같은 과정을 거치게 된다. 

 

 

Merge Sort 예시

 

 

 

 

 

 

---