3. 분할정복 알고리즘

분할정복 방법의 원리

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

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

 

- 특징

- 분할된 작은 문제는 원래 문제와 동일

-> 단, 입력 크기만 작아짐

- 분할된 문제는 서로 독립적

-> 순환적 분할 및 결과 결합이 가능

 

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

- 분할 : 주어진 문제를 여러 개의 작은 문제로 붑ㄴ할

- 정복 : 작은 문제들을 순환적으로 분할, 만약 작은 문제가 더 이상 분할되지 않을 정도로

크기가 충분히 작다면 순환 호출 없이 작은 문제에 대한 해를 구함

- 결합 : 작은 문제에 대해 정복된 해를 결합하여 원래 문제의 해를 구함

 

적용 알고리즘에서의 분할 과정

- 이진탐색, 합병 정렬, 퀵 정렬, 선택 문제

- 이진 탐색 : 분할된 한 쪽만 사용

- 합병 정렬 : 분할된 쪽 다 사용

- 퀵 정렬 : 크기가 동일하지 않게 분할, 다 사용

- 선택 문제 : 크기가 동일하지 않게 분할하고 한쪽만 사용

 

이진 탐색 개념과 원리

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

- 오른차순으로 정렬되었다고 가정

- 탐색 방법

- 배열의 가운데 원소와 탐색키 x를 비교

1) 탐색키 = 가운데 원소 -> 탐색 성공

2) 탐색키 < 가운데 원소 -> 이진탐색(크기 1/2의 왼쪽 부분배열) 순환 호출

3) 탐색키 > 가운데 원소 -> 이진탐색(크기 1/2의 오른쪽 부분배열) 순환 호출

-> 탐색을 반복할 때마다 대상 원소의 개수가 1/2씩 감소

 

- 분할 : 배열의 가운ㄷ에 원소를 기준으로 왼쪽과 오론쪽 부분배열로 분할

탐색키와 가운데 원소가 같으면, 해당 원소의 배열 인덱스를 반환/종료

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

크면 오른쪽 부분배열을 대상으로 이진 탐색을 순환 호출

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

입력 크기 n일 때 최대 분할 횟수는?

- n/2^k = 1 -? k = log(n) 

- 최대 비교 횟수는? 최대 분할 횟수 + 1

성능 분석

- T(n) = T(n/2) + O(1), T(n)=logn

특징

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

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

- 평균 n/2개의 데이터 이동

- 삽입/삭제가 빈번할 경우 부적절

퀵 정렬

- 특정 원소를 기준으로 주어진 배열을 두 부분배열로 분할하고,

각 부분배열에 대해서 퀵 정렬을 순환적으로 적용하는 방식

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

- 피벗

- 두 부분배열로 분할할 때 기준이 되는 특정 원소

- 보통 주어진 배열의 첫번째 원소로 지정

- 개념과 원리

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

- 분할 : 피벗 기준 두 부분으로 분할

- 정복 : 두 부분에 퀵 정렬 순환적이용, 각 부분배열 정렬

- 결합 : 필요 없음

- 알고리즘

- 두 부분 분할, 왼쪽 정렬, 오른쪽 정렬