분할 정복(Divide & Conquer)

정의

• 문제를 나눌 수 없을 때까지 나눈 후 다시 합병하여 결과를 얻는 알고리즘이다.
• 시간 복잡도는 O(nlong) 를 가진다.

합병 정렬

• 아래와 같이 주어진 정렬을 합병 정렬을 이용하여 정렬한다.

7

5

3

9

1

6

• 정렬을 가운데를 기준으로 더 이상 나누어 지지 않을 때 까지 쪼갠다.(Divde)

• 쪼개질 수 없을 때까지 나눈 후 다시 정렬한다.