분할 정복 알고리즘

원리

주어진 문제를 2개 이상의 작은 문제로 순환적으로 분할하여 각각 해결한 후 다시 각각의 해들을 결합하여 원래 문제를 해결하는 방식

특징

• 입력 크기가 작아짐
• 분리된 작은 문제는 서로 독립적

처리 단계

1. 분할 : 주어진 문제를 작은 문제로 분할
2. 정복 : 작은 문제를 순환적으로 더 이상 분할 되지 않을 정도로 분할 후 작은 문제의 해를 구한다.
3. 결합 : 작은 문제를 해결한 해를 결합하여 원래 문제의 해를 구한다.

• tip! 단 , 결합단계가 없는 문제도 존재

종류

종류	분할 방법	분할 각각 사용 여부
이진탐색	1/2로 분할	각 분할 한 부분 중 하나만 선택
퀵 정렬	a:b 로 분할	각 분할 한 부분 모두
합병정렬	1/2로 분할	각 분할 한 부분 모두
선택문제	a:b 로 분할	각 분할 한 부분 중 하나만 선택

1) 이진탐색

전제 : 정렬된 상태의 입력 데이터(오름처순으로 정렬되어 있다고 가정)

탐색 방법

배열의 가운데 원소 A[mid]와 탐색키(찾고자 하는 값)를 비교
가운데 원소 = A[mid] =(시작인덱스 / 종료 인덱스) / 2 
1. 탐색키 = 가운데 원소 -> 탐색 성공 (인덱스 mid 반환 후 종료)
2. 탐색키 < 가운데 원소 -> 이진탐색(원래크기 / 1/2인 왼쪽 부분배열) 순환호출
3. 탐색키 > 가운데 원소 -> 이진탐색(원래크기 / 1/2인 오른쪽 부분배열) 순환호출

최대 분할 횟수 : n* 1/2^k -> k =log(2)n

!정렬된 상태가 전제이기 때문에 삽입,삭제가 빈번한 응용에는 부적합!

2) 퀵 정렬

특정 원소를 기준으로 두 부분 배열로 분할하고 각 부분 배열에 대해 퀵정렬을 순환적으로 적용
! 피벗(pivot) : 주어진 배열을 두 부분 배열로 분리할 때 기준이 되는 특정 원소

• 보통 주어진 배열의 첫번째 원소로 지정

탐색 방법

피벗이 제자리를 잡도록하여 정렬하는 방식
피벗이 제자리를 잡도록하여 정렬 = 피벗의 왼쪽 부분 배열은 피벗보다 작은 숫자 
						  피벗의 오른쪽 부분 배열은 피벗보다 큰 숫자

A[] : 배열
n : 배열의 크기
QuickSort(A[],n){
	if(n>1){
   	pivot = Partition(A[0...n-1],n); // 두 부분 배열로 분할
       QuickSort(A[0...pivot-1],pivot); // 왼쪽 부분 배열에 대한 순환 호출
       QuickSort(A[pivot+1...n-1],n-pivot-1); // 오른쪽 부분 배열에 대한 순환 호출 
   }
}

int Partition(A[],n){
	Left = 1 ; Right = n-1;
    //A[0] 를 비벗 값으로 설정
    //피벗 보다 큰 위치의 값을 찾음
    try{
      while(Left < Right&& A[0]<A[Left]){
          Left++; // 배열의 index 를 넘어가는 경우 발생 (피봇 보다 큰 값이 없을경우)
      }
      //피벗 보다 작은 위치의 값을 찾음
      while(Left > Right&& A[0]>A[Right]){
          Right--; // right = -1 이 되는 경우 발생(피봇 보다 작은 값이 없을경우)
      }
      //작은 위치와 큰 값의 위치를 변경
      if(Left < Right) A[Left]<->A[Right] // 교환
      else A[0]<->A[Right] // 피벗과 최종적인 작은 위치의 값을 교환
    }catch(IndexOutOfBoundsException e){
    	if(Left > n ) A[0]<->A[Right]
        if(Right == -1) Right = 0;//index 0 번째 자리 확정
    }
    return Right; // 피벗의 index 값을 반환
}

[가장 최악의 경우]

• 극심한 불균형적 분할
  - 피벗이 항상 부분 배열의 최솟값 또는 최댓값이 되는 경우
  - 입력 데이터가 정렬된 경우
  - O(n^2)
  

[가장 최선의 경우]

• 가장 균형적인 분할
  - 피벗을 중심으로 항상 동일한 크기의 두 부분 배열로 분할 되는 경우
  - 피벗이 항상 부분 배열의 중간 값이 되는 경우
  - O(nlogn)
  

[가장 평균적인 경우]

• 부분 배열의 모든 분할 비율에 따른 수행시간의 평균
• O(nlogn)

=> 피벗의 선택의 임의성만 보장되면 평균 성능을 보일 가능성이 매우 높다.
(배열의 임의의 값을 선택한 후 , 배열의 첫 원소와 서로 교환 후 정렬 수행)