기록하는 곳

분할 정복 알고리즘 (Divide and Conquer)

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

  1. 주어진 문제의 입력을 더 이상 나눌 수 없을 때까지 두 개 이상의 작은 문제로 순환적으로 분할한다.
  2. 이렇게 분할된 작은 문제들을 각각 해결한 후 이 해들을 결합해서 원래 문제의 해를 구하는 방식

특징

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

처리 과정

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

이진 탐색

정렬된 상태의 입력 데이터에 대해 절반씩 나눠 한쪽만 탐색하는 방법이다.

탐색 방법

배열 가운데의 원소 A[mid]와 탐색키 x를 비교

  1. 탐색키 = A[mid] => 탐색 성공 (인덱스 mid 반환 후 종료)
  2. 탐색키 < A[mid] => 이진 탐색 (인덱스 mid 기준 왼쪽 탐색)
  3. 탐색키 > A[mid] => 이진 탐색 (인덱스 mid 기준 왼쪽 탐색)

위와같이 탐색을 진행한다. 탐색을 반복할 수록 원소의 개수가 절반으로 감소한다.

타겟넘버의 인덱스를 리턴하는 예제

const arr = [1, 2, 3, 4, 5, 6, 7]

function binarySearch(arr, target) {
  let low = 0;
  let high = arr.length - 1

  while(low <= high) {
      const mid = Math.floor((low+high) / 2)

      if (arr[mid] === target) {
          return mid;
      } else if (arr[mid] > target) {
          high = mid - 1;
      } else {
          low = mid + 1;
      }
  }

  return null
}

단점

  • 입력 배열의 데이터가 정렬된 경우에만 적용 가능
  • 삽입 / 삭제 연산은 부가적인 데이터 이동을 수반함
    • 데이터의 정렬 상태 유지를 위해서 평균 n/2개의 데이터 이동이 발생
      (삽입 / 삭제가 빈번한 응용에서는 부적합함)
  • 시간 복잡도 : T(n) = T(n/2) + O(1) = O(logn)

퀵 정렬

  • 피벗 : 리스트 안에 있는 선택된 한 요소

탐색 방법

  1. 피벗을 기준으로 작은 원소들은 왼쪽으로 이동
  2. 피벗을 기준으로 큰 원소들은 오른쪽으로 이동
  3. 왼쪽부터 다시 퀵정렬을 하여 정복될 때까지 계속 왼쪽은 분할한다.
  4. 위로 다시 거슬러 올라가며 오른쪽도 정복해준다.

최악의 경우

  • 배열이 항상 0:n-1 또는 n-1:0으로 분할되는 경우
    (피벗이 항상 부분배열의 최솟값 또는 최댓값이 되는 경우)
    (=입력 데이터가 정렬되어 있는 경우)
  • 최악일 때 시간복잡도 : T(n) = O(n^2)
  • 피벗 선택의 임의성만 보장되면 최악의 경우가 나올 확률이 매우 적음

최선의 경우

  • 피벗을 중심으로 항상 동일한 크기의 두 부분배열로 분할되는 경우
    (피벗이 항상 부분배열의 중간값이 되는 경우)
  • 최선일 때 시간복잡도 : T(n) = O(nlogn)
Last Updated: