분할정복 방법의 원리

분할 정복 방법의 원리

• 순환적으로 문제를 푸는 하향식 접근 방법

  • 주어진 문제의 입력을 더 이상 나루 수 없을 때까지 두 개 이상의 작은 문제로 순환적으로 분할하고, 이렇게 분할된 작은 문제들을 각각 해결한 후 그 해를 결합하여 원래 문제의 해를 구하는 방식

• 특징

  • 분할된 작은 문제는 원래 문제와 동일
    • 단, 입력 크기만 작아짐
  • 분할된 문제는 서로 독립적
    • 순환적 분할 및 결과 결합이 가능

• 각 순환 호출 시의 처리 과정

  • 분할: 주어진 문제를 여러 개의 작은 문제로 분할
  • 정복: 작은 문제들을 순환적으로 분할. 만약 작은 문제가 더 이상 분할되지 않을 정도로 크기가 충분히 작다면 순환 호출없이 작은 문제에 대한 해를 구함
  • 결합: 작은 문제에 대해 정복된 해를 결합하여 원래 문제의 해를 구함

이진 탐색

개념과 원리

• 정렬된 상태의 데이터에 대해 적용 가능한 효과적인 탐색 방법

  • 오름차순으로 정렬되었다고 가정

• 탐색 방법

  • 배열의 가운데 원소와 탐색키 x를 비교
    1. 탐색키 = 가운데 원소 -> 탐색 성공
    2. 탐색키 < 가운데 원소 -> 이진 탐색(크기 1/2의 왼쪽 부분배열) 순환 호출
    3. 탐색키 > 가운데 원소 -> 이진 탐색(크기 1/2의 오른쪽 부분배열) 순환 호출
  • 탐색을 반복할 때마다 대상 원소의 개수가 1/2씩 감소

• 분할: 배열의 가운데 원소를 기준으로 왼쪽과 오른쪽 부분배열로 분할. 탐색키와 가운데 원소가 같으면 해당 원소의 배열 인덱스를 반환 종료

• 정복: 탐색키 x가 가운데 원소보다 작으면 왼쪽 부분배열을 대상으로 이진 탐색을 순환 호출, 크면 오른쪽 부분배열을 대상으로 이진 탐색을 순환 호출

• 결합: 부분배열에 대한 탐색 결과가 직접 반환되므로 결합이 불필요

알고리즘 순환 형태

function BinarySearch(arr, left, right, x) {
  if (left > right) return -1;
  const mid = Math.floor((left + right) / 2);
  if (x === arr[mid]) return mid;
  else if (x < mid) BinarySearch(arr, left, mid - 1, x);
  else BinarySearch(arr, mid + 1, right, x);
}

알고리즘 반복 형태

function BinarySearch(arr, n, x) {
  let left = 0;
  let right = n - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (x === arr[mid]) return mid;
    else if (x < mid) right = mid - 1;
    else left = mid + 1;
  }
  return -1;
}

이진 탐색에서의 분할과 비교

• 입력 크기 n 일때 최대 분할 횟수: n / 2^k = 1 -> k = log n

• 최대 비교 횟수: 최대 분할 횟수 + 1

성능 분석

• T(n) = 입력 크기 n에 대한 탐색 과정에서의 모든 비교 횟수의 합 = 맨 바깥 수준에서의 비교 횟수 + 순환 호출에서의 비교 횟수: T(n) = logn

특징

• 입력이 정렬된 리스트에 대해서만 적용 가능

• 삽입/삭제 연산 시 데이터의 정렬 상태 유지가 필요

  • 평균 n/2개의 데이터 이동이 발생 -> 삽입/삭제가 빈번한 응용에는 부적합

퀵 정렬

개념과 원리

• 특정 원소를 기준으로 주어진 배열을 두 부분배열로 분할하고 각 부분배열에 대해서 퀵 정렬을 순환적으로 적용하는 방식

  • 오름차순으로 정렬한다고 가정

• 피벗

  • 두 부분배열로 분할할 떄 기준이 되는 특정 원소
    • 보통 주어진 배열의 첫 번쨰 원소로 지정

• 피벗이 제자리를 잡도록 하여 정렬하는 방식

  • 왼쪽 부분배열의 모든 값 < 피벗 < 오른쪽 부분배열의 모든 값

• 분할: 피벗을 기준으로 주어진 배열을 두 부분배열로 분할

• 정복: 두 부분배열에 대해서 퀵 정렬을 순환적으로 적용하여 각 부분배열을 정렬

• 결합: 필요 없음

알고리즘 퀵 정렬

function QuickSort(arr, n) {
  if (n > 1) {
    const pivot = Partition(arr[0, ... , n - 1], n);    // 두 부분배열로 분할
    QuickSort(arr[0, ... , pivot - 1], pivot);          // 왼쪽 부분배열에 대한 순환 호출
    QuickSort(arr[pivot + 1, ... , n - 1], n - pivot -1);   // 오른쪽 부분배열에 대한 순환 호출
  }
}
function Partition(arr, n) {
  let left = 1;
  let right = n- 1;
  while(left < right) {     // 피벗 arr[0]
      while(left < n && arr[left] < arr[0]) left++;
      while(right > 0 && arr[right] >= a[0]) right--;
      if (left < right) swap(arr[left], arr[right]);
      else swap(arr[0], arr[right])
  }
  return right;
}

성능 분석

• 퀵 정렬 QuickSort 수행 시간
  • 한 번의 분할 Partition + 두 번의 QuickSort 순환 호출

성능 분석 최악의 경우

• 피벗만 제자리를 잡고, 나머지 모든 원소가 하나의 부분배열로 분할되는 경우

• 극심한 불균형적 분할

  • 피벗만 제자리를 잡고, 나머지 모든 원소가 하나의 부분배열이 되는 경우
  • 피벗이 항상 부분배열의 최솟값 또는 최댓값이 되는 경우
  • 입력 데이터가 정렬된 경우 그리고 피벗을 배열의 처음 원소로 지정한 경우
  • T(n) = O(n^2)

성능 분석 최선의 경우

• 피벗을 중심으로 항상 동일한 크기이 두 부분배열로 분할되는 경우

• 가장 균형적인 분할

  • 피벗을 중심으로 항상 동일한 크기의 두 부분배열로 분할되는 경우
  • 피벗이 항상 부분배열의 중간값이 되는 경우
  • T(n) = O(nlogn)

성능 분석 평균적인 경우

• 부분 배열의 모든 분할 비율에 따른 수행 시간의 평균
  • 피벗은 동일한 확률로서 분할 후 배열의 어느 곳에나 위치 가능
  • T(n) = O(nlogn)

특징

• 최선/평균의 경우 -> O(nlogn)

• 최악의 경우 -> O(n^2)

  • 피벗 선택의 임의성만 보장되면 평균적인 성능을 보일 가능성이 매우 높음
    • 배열에서 임의로 값을 선택해서 배열의 처음 원소와 서로 교환한 후 정렬 수행