[algorithm] 분할정복 알고리즘

• 분할정복 방법
  • 순환적으로 문제를 푸는 하향식 접근방법
    • 주어진 문제의 입력을 더이상 나눌 수 없을 때까지 두 개 이상의 작은 문제로 순환적으로 분할하고
    • 분할된 작은 문제들을 각각 해결한 후 이 해들을 결합해서 원래 문제의 해를 구하는 방식
  • 특징
    • 분할된 작은 문제는 원래 문제와 동일
      • 단, 입력 크기만 작아짐
    • 분할된 작은 문제는 서로 독립적
      • 순환적 분할 및 결과 통합이 가능
  • 분할정복 방법의 처리 단계
    • 각 순환 호출마다 세 단계의 처리과정을 거침
      • 분할: 주어진 문제를 여러 개의 작은 문제로 분할한다.
      • 정복: 작은 문제를 순환적으로 분할, 만약 작은 문제가 더이상 분할되지 않을 정도로 크기가 충분히 작다면 순환호출 없이 작은 문제의 해를 구함
      • 결합: 작은 문제에 대해 정복된 해를 결합하여 원래 문제의 해를 구함

•  
  • 이진탐색
    • 정렬된 상태의 입력 데이터에대한 효과적인 탐색 방법
      • 오름차순으로 정렬되었다고 가정
    • 탐색방법
      • 배열의 가운데 원소 A[mid]와 탐색키 x를 비교
      • (1) 탐색키 = 가운데 원소 -> 탐색 성공(인덱스 mid 반환 후 종료)
      • (2) 탐색키 < 가운데 원소 -> 이진 탐색(원래 크기 1/2인 왼쪽 부분배열)' 순환 호출
      • (3) 탐색키 > 가운데 원소 -> 이진 탐색(원래 크기 1/2인 오른쪽 부분배열) 순환 호출
        • 탐색을 반복할 때마다 대상 원소의 개수가 1/2씩 감소
      • 분할: 배열의 가운데 원소를 기준으로 왼쪽 오른쪽 부분배열로 분할. 탐색키와 가운데 원소가 같으면 가운데 원소의 배열 인덱스를 반환, 종료
      • 정복: 탐색키가 가운데 원소보다 작으면 왼쪽 부분배열을 대상으로 이진 탐색을 순환 호출, 크면 오른쪽 부분배열을 대상으로 이진 탐색을 순환 호출
      • 결합: 불필요(부분배열에 대해 탐색 결과가 직접 반환)

    BinarySearch_Iteration(A[], n, x){
        Left = 0; Right = n-1;
        while(Left<=Right){
            Mid = (Left+Right)/2;
            if(x==A[Mid]) return Mid;
            else if(x<A[Mid]) Right = Mid - 1;
            else Left = Mid + 1;
        }
        return -1;
    }

 

•  
  • 이진탐색에서의 분할 및 비교 횟수
    • 입력 크기 n일 때 최대 분할 횟수
      • 최대 비교 횟수 -> "최대 분할 횟수 + 1"

• • T(n) = 입력 크기 n에 대한 탐색 과정에서의 모든 비교 횟수의 합
           = 맨 바깥 수준에서의 비교 횟수 + 순환 호출에서의 비교 횟수
  • T(n) = T(n/2) + O(1) (n>1), T(1) = 1
  • T(n) = O(logn)
  • 특징
    • 입력배열의 데이터가 정렬된 경우에 대해서만 적용 가능
    • 삽입/삭제 연산은 부가적인 데이터 이동을 수반
      • 데이터의 정렬 상태 유지를 위해 평균 n/2개의 데이터 이동이 발생 
        • 삽입/삭제가 빈번한 응용에서는 부적합
•  퀵정렬
  • 특정 원소를 기준으로 주어진 배열을 두 부분배열로 분할하고 각 부분배열에 대해서 퀵 정렬을 순환적으로 적용하는 방식
    • 오름차순으로 정렬한다고 가정
  • 피벗
    • 주어진 배열을 두 부분배열로 분할할 때 기준이 되는 특정 원소
      • 보통 주어진 배열의 첫 번째 원소로 지정
  • 피벗이 제자리를 잡도록 하여 정렬하는 방식
  • 분할: 피벗을 기준으로 주어진 배열을 두 부분배열로 분할한다.
  • 정복: 두 부분배열에 대해 퀵 정렬을 순환적으로 적용하여 각 부분배열을 정렬한다.
  • 결합: 필요없음 
  • 성능분석
    •  분할 함수 Partition() 수행시간
      • 피벗과의 비교 횟수
        • 데이터를 바꾸지 않는 경우 1번, 데이터를 바꾸는 경우 2번 수행함
          • n에 비례 -> O(n)
    • 퀵 정렬 QuickSort() 수행시간
      • T(n) = T(leftside) + T(rightside) + O(n) (n>1)
      • T(1) = O(1)
    • 성능분석_최악의 경우
      • 배열이 항상 0:n-1 또는 n-1:0으로 분할되는 경우
      • 극심한 불균형적 분할
        • 0:n-1, n-1:0 -> 피벗만 제자리를 잡고 나머지 모든 원소가 하나의 부분배열이 되는 경우
        • 피벗이 항상 부분배열의 최솟값 또는 최댓값이 되는 경우
        • 입력데이터가 정렬된 경우 AND 피벗을 배열의 처음 원소를 정한 경우
          • T(n) = O(n^2)
    • 성능분석_최선의 경우
      • 가장 균형적인 분할
        • 피벗을 중심으로 항상 동일한 크기의 두 부분배열로 분할되는 경우
        • 피벗이 항상 부분배열의 중간값이 되는 경우
      • T(n) = O(nlogn)
    • 성능분석_평균적인 경우
      • 부분배열의 모든 분할 비율에 따른 수행시간의 평균
        • 피벗은 동일한 확률로서 분할 후 배열의 어느 곳에나 위치 가능
      • T(n) = O(nlogn)
    • 최선/평균 수행시간 -> O(nlogn)
    • 최악 수행 시간 -> O(n^2)
      • 피벗 선택의 임의성만 보장되면 평균 성능을 보일 가능성이 매우 높음
        • 배열에서 임의의 값을 선택한 후 배열의 처음 원소와 서로 교환한 후 정렬 수행

int Partition(A[], n){
    Left = 1; Right = n-1;
    while(Left < Right) { // 피벗 A[0]
        // 피벗보다 큰 값의 위치를 찾음
        while(Left < n && A[Left] < A[0]) Left++;
        // 피벗보다 작은 값의 위치를 찾음
        while(Right > 0 && A[Right] >= A[0]) Right--;
        if(Left < Right) // A[Left] <=> A[Right] 교환
        else // 교환 A[0] <=> A[Right]
    }
    return Right;
}