분할정복 알고리즘(1)

분할 정복 알고리즘

• 큰 문제를 여러 부분문제로 나누어 각 부분문제에 동일한 알고리즘을 적용하여 부분해를 각각 구해 정복(취합)하여 문제를 해결하는 방법
• 분할은 더 이상 분해가 될 수 없을 때까지 분할한다.
• 입력의 크기가 n, 총 분할 회수는 k라고 할 때
  n/2^k 일때 더 이상 분할할 수 없음. => k = log2⁡n이다.
• 분할만 하면 답을 구할 수 있는 것이 아니라 취합(정복)과정도 필요하다.
• 종류 : 합병정렬, 행렬곱셈, 퀵 정렬, 이진탐색, 선택 문제 알고리즘, 삽입 정렬...

합병정렬(Merge sort)

• 입력이 2개의 부분문제로 분할되고, 부분문제의 크기가 1/2로 감소하는 분할 정복 알고리즘
• 두 부분문제의 크기가 같다!
• 각각의 부분문제를 재귀적으로 합병 정렬(순환호출방식)
• 2개의 정렬된 부분을 합병하여 정복한다.

<pseudo code>
MergeSort(A,p,q)
입력 : A[p]~A[q]
출력 : 정렬된 A[p]~A[q]

if(p<q){ //배열의 원소가 2개 이상(1개면 그 자체로 정렬 완료)
k = ⌊(p+q)/2⌋ // 중앙에 있는 원소의 index구하기
MergeSort(A,p,k) // 부분문제 중 앞부분 재귀호출(분할 할 수 없을 때까지)
MergeSort(A,k+1,q)// 부분문제 중 뒷부분 재귀호출(분할 할 수 없을 때까지)
A[p]~A[k]와 A[k+1]~A[q]를 합병한다. 

• 계속 재귀호출하여 분할할 때, 분할 할 수 없을 때까지 분할 후 정렬까지가 한 세트다.
• 합병 정렬의 시간복잡도 = {한 층마다의 비교 시간복잡도}*{층 수}
• O(n)*log2⁡n = O(nlog2n)

퀵 정렬(Quick Sort)

• 각 부분문제의 크기가 일정하지 않은 형태의 분할 정복 알고리즘(합병 정렬은 부분문제의 크기가 같았다.
• 피봇(pivot) : 다양한 규칙으로 정하는 기준 원소
• 피봇을 기준으로 피봇보다 작은 숫자들을 왼쪽으로, 피봇보다 큰 숫자들을 오른쪽에 위치하도록 분할하고 피봇은 그 두 부분문제의 사이에 놓는다.
  피봇은 왼쪽이나 오른쪽 부분에 포함되지 않는다.
• 정렬 수행 방법

1. left, right포인터를 설정한다.
2. 임의의 피봇을 정한다.
3. 피봇과 가장 앞에 있는 원소의 자리를 바꾼다.
4. left는 한 칸씩 오른쪽으로 이동하다 피봇보다 큰 수를 만나면 stop
5. right는 한 칸씩 왼쪽으로 이동하다가 피봇보다 작은 수를 만나면 stop
6. stop한 left와 right의 원소 두 개의 자리를 바꾼다.
7. 두 개의 포인터가 겹칠 때까지 반복한다.
8. 겹친다면, 겹친 원소의 바로 직전 원소와 피봇의 자리를 바꾼다.
9. 피봇보다 작은 그룹과 피봇보다 큰 그룹에서 재귀적 호출로 다시 임의의 피봇을 구해 정렬을 한다.

• 퀵 정렬의 성능은 피봇 선택이 좌우한다. 한 부분(피봇의 값이 너무 크거나 작으면)으로 치우치게 됨
• 퀵 정렬의 최악의 경우 시간복잡도 : O(n^2)
• 퀵 정렬의 최선 경우 시간복잡도 : O(nlog2n) - 합병정렬처럼 나눠진 경우
• 평균 경우 시간복잡도 : O(nlog2n)
• 입력의 크기가 클 때는 퀵 정렬이 빠르지만, 입력의 크기가 작아지면 퀵 정렬이 삽입정렬보다 빠르지 않다. => 어느 정도의 규모까지는 퀵정렬로 분할하고, 그 다음은 삽입정렬을 사용하면 더 효율적이다.

선택문제(Selection)

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

1. 퀵 정렬과 같이 피봇을 기준으로 작은그룹, 큰 그룹으로 나누고, 각 그룹의 크기를 구한다.
2. 크기롸 k를 비교 후에 구하고자 하는 수가 있는 그룹으로 가서 k값을 변화시키고 다시 퀵 정렬을 이용해 분할 한다.

• good/bad 분할 : 분할된 부분그룹의 하나의 크기가 입력 크기의 3/4이상인 경우 나쁜(bad)분할이라고 정의, 좋은 분할은 이와 반대
• 피봇을 랜덤하게 정했을 때 god분할이 될 확률은 1/2, 평균 2회 연속해서 랜덤하게 피봇을 정하면 good분할을 할 수 있다.
• good분할만 이루어졌을 때만의 시간복잡도 : O(n), 선택 알고리즘의 평균 시간복잡도 : 2*O(n) = O(n)
• 선택 알고리즘은 부분문제들을 취합하는 과정이 별도로 필요없다. 원하는 부분만 계속해서 분할하고 값을 찾아가지 해당되지 않는 부분은 신경쓰지 않는다. (이진 탐색과 유사)