3강 분할정복 알고리즘(1)

분할정복 방법의 원리

• 분할정복 방법이란?
  순환적으로 문제를 푸는 하향식 접근 방법이다.
  주어진 문제의 입력을 더 이상 나눌 수 없을 때까지 두 개 이상의 작은 문제로 순환적으로 분할하고 이렇게 분할된 작은 문제들을 각각 해결한 후 이 해들을 결합해서 원래 문제의 해를 구하는 방식이다.

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

• 처리 단계
  

  1. 분할
     여러개의 작은 문제로 분활
  2. 정복
     더 이상 분할할 수 없을정도의 작은 문제가 되면 해를 구한다
  3. 결합 (문제에 따라 결합 단계가 필요 없을 수도 있다)
     해를 결합하여 원래 문제의 해로 결합한다

• 분할정복의 대표적인 알고리즘 문제

  1. 이진 탐색
     절반으로 쪼갠 후 한쪽은 처리하지 않는다
  2. 합병 정렬
     절반으로 쪼갠 후 양쪽다 처리한다
  3. 퀵 정렬
     절반으로 쪼개지만 일정하지 않는 크기로 쪼개서 양쪽다 처리한다
  4. 선택 문제
     크기가 일정하지 않는 두개로 쪼개서 한쪽은 처리하지 않는다

이진탐색

• 정렬된 상태의 입력 데이터에 대한 효과적인 탐색 방법이다.
  (오름차순으로 정렬되어 있다고 가정한다.)

• 탐색방법
  배열의 가운데 원소와 탐색키를 비교한다. (같으면 탐색성공, 탐색키가 작으면 왼쪽부분에 대해 이진탐색, 크면 오른쪽부분에 대해 이진탐색을 한다)
  → 탐색을 반복할 때마다 대상 원소의 갯수가 1/2씩 감소한다.

• 탐색 과정

  1. 분할
     가운데 원소를 기준으로 왼쪽 오른쪽으로 분할
  2. 정복
     기준 원소와 탐색키를 비교하여 왼쪽 오른쪽 부분에 대해 필요한 부분에 대해 이진탐색을 순환 호출한다.
  3. 결합 x

• 이진탐색에서의 분할 및 비교 횟수
  최대 분할 횟수: log n
  최대 비교 횟수: log n + 1

• 특징

  1. 입력 배열의 데이터가 정렬된 경우에서만 적용 가능하다
  2. 삽입/삭제 연산은 부가적인 데이터이동을 수반하기 때문에 빈번한 경우 적합하지 않다

퀵 정렬

• 특정 원소를 기준으로 주어진 배열을 두 부분배열로 분할하고, 각 부분배열에 대해서 퀵 정렬을 순환적으로 적용하는 방식이다.
  (오름차순으로 정렬한다고 가정한다)

• 피벗: 주어진 배열을 두 부분배열로 분할할 때 기준이 되는 원소
  (보통 주어진 배열의 첫번째 원소를 피벗으로 한다)

• 탐색 과정
  1. 분할
     피벗을 기준으로 주어진 배열을 두 부분배열로 분할한다
  2. 정복
     두 부분배열에 대해 퀵 정렬을 순환적으로 적용하여 정렬한다
  3. 결합 x
• 특징
  최선/평균 수행 시간 → O(nlogn)
  최악 수행 시간 → O(n**2)
  피벗 선택의 임의성만 보장되면 평균 성능을 보일 가능성이 매우 높다.