[문제 해결 알고리즘] 분할 정복 알고리즘 ①

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

 (1) 분할 과정

 - 분할한 입력에 대하여 동일한 알고리즘을 적용하여 해를 계산하며, 이들의 해를 취합하여 원래 문제의 해를 얻음

 - 부분문제 : 분할된 입력에 대한 문제 -> 더이상 분할할 수 없을 때까지 계속 분할함

 - 부분해 : 부분 문제의 해

 - Q : 입력의 크기가 n일 때 몇번 2분할해야 더 이상 분할할 수 없는 크기인 1이 될까?

   A : 분할한 횟수 = k 라고 하자

        k = log(2)n

 (2) 정복 과정

 - 대부분의 분할 정복 알고리즘은 문제의 입력을 단순히 분할만 해서는 해를 구할 수 없음

 - 분할된 부분 문제들을 정복해야함 == 정복해를 찾아야 함

 - 정복하는 방법은 문제에 따라 다르나 일반적으로 부분 문제들의 해를 취합하여 보다 큰 부분 문제의 해를 구함

(3) 분할 정복 알고리즘 분류

 - 합병 정렬, 최근접 점의 쌍 찾기 : 문제가 2개로 분할되고, 부분 문제의 크기가 1/2로 감소하는 알고리즘

 - 퀵 정렬 : 문제가 2개로 분할, 부분 문제의 크기가 일정하지 않은 크기로 감소하는 알고리즘

 - 선택 문제 알고리즘 : 문제가 2개로 분할, 그 중에 1개의 부분문제는 고려할 필요 없으며,

                                   부분 문제의 크기가 일정하지 않은 크기로 감소하는 알고리즘

2. 합병 정렬

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

 - n개의 숫자들을 n/2개씩 2개의 부분문제로 분할함 > 각각의 부분 문제를 재귀적으로 합병 정렬함

 - 2개의 정렬된 부분을 합병하여 정렬(정복)함

 - 합병 : 2개의 각각 정렬된 숫자들을 1개의 정렬된 숫자들로 합치는 것

(1) 합병 정렬 알고리즘 의사 코드 MergeSort(A, p, q)

  ⓐ  if(p<q) // 정렬할 부분의 원소의 수가 2개 이상일 때에만 다음 단계 수행

  ⓑ   k = |(p+q)/2| // k = 반으로 나누기 위한 중간 원소의 인덱스, 나머지 버림

  ⓒ  MergeSort(A,p,k)  // 앞부분 재귀 호출

  ⓓ  MergeSort(A,k+1,q)  // 뒷부분 재귀 호출

  ⓔ  A[p]~A[k]와 A[k+1]~A[q]의 합병

3. 분할 합병 정렬 복잡도

 - 분할하는 부분은 배열의 중간 인덱스 계산과 2번의 재귀 호출이므로 O(1)시간 소요됨

 - 합병의 수행 시간은 이력의 크기에 비례함

 - 2개의 정렬된 배열 A, B의 크기가 각각 n, m이라면, 최대 비교 횟수 = n+m-1

 - 각 층에서 수행된 비교 횟수는 O(n)임

 - 합병 정렬의 시간 복잡도 O(nlogn)

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

 : 입력을 위한 메모리 공간(입력 배열)외에 추가로 입력과 같은 크기의 공간(임시배열)이 별도로 필요함

   == 합병된 결과를 저장할 곳이 필요함

4. 퀵정렬 알고리즘

 - 문제를 2개의 부분 문제로 분할하는데 각 부분문제의 크기가 일정하지 않은 형태의 분할 정복 알고리즘

 - 피봇이라 일컫는 배열의 원소(숫자)를 기준으로 피봇보다 작은 숫자를 왼편으로, 큰 숫자를 오른편으로 위치하도록 분할하고 피봇을 그 사이에 넣음

 - 분할된 부분 문제들에 대해서도 위와 동일한 과정을 재귀적으로 수행하여 정렬함

 - 피봇은 분할된 왼편이나 오른편 부분에 포함하지 않음

 - Quick Sort(A, left, right)

   입력 : A[left]~A[right]

   출력 : 정렬된 배열 A[left]~A[right]

   ⓐ if(left<right)

   ⓑ 피봇을 A[left]~A[right] 중에 선택 

        - 피봇을 A[left]와 자리를 바꾼 후 배열의 각 원소를 비교하여 피봇보다 작은 숫자들은 A[left]~A[p-1]로 옮김

        - 피봇보다 큰 숫자들은 A[p+1]~A[right]로 옮기며, 피봇은 A[p]에 놓음

   ⓒ QuickSort(A, left, p-1)

   ⓓ QuickSort(A,p+1,right)

  5. 퀵정렬 복잡도 : 피봇 선택이 좌우함

  - 피봇이 가장 작은 숫자 또는 가장 큰 숫자가 선택되면 한 부분으로 치우치는 분할을 야기함

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

  - 최선의 경우 O(nlogn) : 피벗이 값을 반씩 잘 나눌 때

  - 퀵정렬은 커다란 크기의 입력에 대해서 가장 좋은 성능을 보이는 정렬 알고리즘임

  - 퀵정렬은 실질적으로 어느 정렬 알고리즘보다 좋은 성능을 보임

  - 추가 임시 저장소가 불필요함