분할 정복 방법
- 순환적으로 문제를 푸는 하양식 접근 방법
- 주어진 문제의 입력을 더 이상 나눌 수 없을 때까지 작은 문제로 순환적으로 분할하고, 이렇게 분할된 작은 문제들은 각각 **해결(정복)**한 후 이 해들을 결합해서 원래 문제의 해를 구하는 방식
- 특징
- 분할된 작은 문제는 원래 문제와 동일 (단, 입력 크기만 작아짐)
- 분할된 작은 문제는 서로 독립적 (순환적 분할 및 결과 통합이 가능)
- 단계
- 분할 : 주어진 문제를 여러 개의 작은 문제로 분할
- 정복 : 작은 문제를 순환적으로 분할 (충분히 작다면 순환 호출 없이 작은 문제의 해를 구함)
- 결합 : 작은 문제에 대해 정복된 해를 결합하여 원래 문제의 해를 구한다.
- 분할 정복을 적용한 알고리즘
이진 탐색(binary search)
- 정렬된 상태로 주어진 원소들을 절반 씩 줄여가면서 원하는 키 값을 찾는 문제
- 탐색을 수행할 때마다 탐색 대상이 되는 원소의 개수가 1/2씩 감소
- 특징
- 정렬된 상태의 입력 데이터 (default: 오름차순)
- 삽입 / 삭제 연산은 부가적인 데이터 이동을 수반
- 데이터의 정렬 상태 유지를 위해서 평균 n/2개의 데이터 이동이 발생
- 탐색 방법 : mid = (시작 인덱스 + 마지막 인덱스) / 2
- 최대 비교 횟수 : 최대 분할 횟수 + 1
퀵 정렬
- 특정 원소를 기준으로 주어진 배열을 두 부분 배열로 분할하고, 각 부분 배열에 대해서 퀵 정렬을 순환적으로 적용하는 방식 (오름차순으로 정렬한다고 가정)
- 피벗(pivot)
- 주어진 배열을 두 부분 배열로 분할할 때 기준이 되는 특정 원소
- 보통 주어진 배열의 첫 번째 원소로 지정
- 단계
- 분할 : 피벗을 기준으로 주어진 배열을 두 부분 배열로 분할
- 정복 : 두 부분 배열에 대해서 퀵 정렬을 순환적으로 적용하여 각 부분 배열을 정렬
- 결합 : 필요 없음
- 최악의 수행 시간을 가지는 경우
- 피벗만 제자리를 잡고 나머지 모든 원소가 하나의 부분 배열이 되는 경우
- 피벗이 항상 부분 배열의 최솟값 또는 최댓값이 되는 경우
- 입력 데이터가 정렬된 경우 AND 피벗을 배열의 처음 원소로 정한 경우
- 최악의 수행 시간 : T(n) = O(n2)
