분할 정복 알고리즘(Divide and Conquer Algorithm) 이론

분할 정복 알고리즘

 주어진 문제의 입력을 분할하여 문제를 해결(정복)하는 방식의 알고리즘

분류

     분할되는 부분문제의 수와 부분문제의 크기에 따라 분류

1) 합병 정렬(Merge Sort)

2) 퀵 정렬(Quick Sort)

3) 선택 문제(Selection)

4) 최근접 점의 쌍 찾기(Closest Pair)

1) 합병 정렬 (Merge Sort)

정의 : 입력이 2개의 부분문제로 분할되고, 부분문제의 크기가 1/2로 감소하는 분할 정복 알고리즘

합병의 시간복잡도 : 2개의 정렬된 두 배열의 크기가 각각 n, m 일때, 최대 비교 횟수는 n+m-1, 시간복잡도는 O(n+m)

합병 정렬의 공간복잡도 : O(n)

합병 정렬의 시간복잡도 : 층수 X O(n) = log2n X O(n) = O(nlogn)

외부 정렬의 기본이 되는 정렬 알고리즘이며 연결 리스트에 있는 데이터를 정렬할 때에도 퀵 정렬이나 힙 정렬보다 훨씬 효율적이다.

1. 분할 단계

2. 병합 단계

2) 퀵 정렬 (Quick Sort)

정의 : 2개의 부분문제로 분할하나 각 부분문제의 크기가 일정하지 않은 형태의 분할 정복 알고리즘,

  정복 후 분할하는 특징이 있으며, 이 정렬을 수행하기 위해 다시 정렬(Sort)를 해주어야 하는 문제가 있다.

  (이에 대한 문제의 해결법은 제일 작은것을 k번 빼서 다른 메모리 공간에 저장하면 된다. 그러면 k번 비교하는 셈이 된다.)

최악 경우 시간복잡도 : O(n^2)

최선 경우 시간복잡도 : 피봇과의 비교횟수 X 층수 = O(n) X log2n = O(nlog2n)

피봇 선정 방법

 퀵 정렬의 불균형한 분할을 완화하기 위해 생긴 방법

1) 랜덤

2) 세 숫자의 중앙값으로 선정하는 방법 : 가장 왼쪽, 중간, 가장 오른쪽 숫자 중에서 중앙값을 피봇으로 정한다.

ex) 가장 왼쪽 숫자 11, 중간 숫자 1, 가장 오른쪽 숫자 20이라고 할때 가장 중간에 가까운 11을 피봇으로 정한다.

3) 선택 문제 (Selection)

정의 : n개의 숫자들 중에서 k번째로 작은 숫자를 찾는 문제

  퀵 정렬의 방법을 이용함

  이진탐색과 유사함 (= 선택 범위를 1/2로 줄여가며 찾고자 하는 숫자를 찾아감)

평균 경우 시간복잡도 : 2 X O(n) = O(n)

(2를 곱한 이유는 평균 2번만에 good 분할이 되기 때문)

4) 최근접 점의 쌍 찾기(Closest Pair)

정의 : 2차원 평면상의 n개의 점이 입력으로 주어질 때, 거리가 가장 가까운 한쌍의 점을 찾는 문제