[방송대 알고리즘]분할정복 알고리즘

※ 방송대 교재의 예제를 참고하여 작성하였습니다. 디테일한 내용은 교재를 참고 바랍니다.

분할정복 알고리즘

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

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

• 분할된 작은 문제는 서로 독립적, 순환적 분할 및 결과 통합이 가능
• 분할된 작은 문제는 원래 문제와 동일

분할정복 방법의 처리 과정

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

결합 단계가 없는 문제도 존재한다.

대표적인 알고리즘

이진탐색

• 문제를 절반으로 나누고, 절반은 처리하지 않음

합병정렬

• 문제를 절반으로 자르고, 자른 문제를 모두 처리

퀵정렬

• 문제를 자르는데 그 크기가 일정하지 않음

선택 문제

• 문제를 자르는데 그 크기가 일정하지 않음, 자른 부분중 한 부분은 처리하지 않음

이진탐색

정렬된 상태의 입력 데이터에 대한 효과적인 탐색 방법(예제에서는 오름차순으로 정렬되었다고 가정)

탐색방법

• 배열의 가운데 원소 A[mid]와 탐색키 x를 비교
• 탐색키 = 가운데 원소 → 탐색 성공(인덱스 mid 반환 후 종료)
• 탐색키 < 가운데 원소 → 이진탐색(원래 크기의 1/2인 왼쪽 부분배열) 순환 호출
• 탐색키 > 가운데 원소 → 이진탐색(원래 크기의 1/2인 오른쪽 부분배열) 순환 호출

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

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

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

결합: 필요 없음

최대 분할 횟수: floor(logn)

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

퀵정렬

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

피벗: 주어진 배열을 두 부분배열로 분할할 때 기준이 되는 특정 원소, 보통 주어진 배열의 첫 번째 원소로 지정

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

피벗을 잡고 피벗의 왼쪽에는 피벗의 값보다 작은 값들이 오게 하고, 피벗의 오른쪽에는 피벗의 값보다 큰 수들이 오게 하는것을 반복한다.

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

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

결합: 필요 없음

퀵정렬의 핵심은 ‘분할함수’ 어떻게 분할시킬지가 가장 중요하다.

분할함수의 마지막배열+1 의 위치에는 inf값이 있다고 가정한다.

피벗과의 비교 횟수: n

퀵정렬의 수행 시간

• 배열이 0:n-1 또는 n-1:0으로 분할된 경우: n^2, 최악의 경우, 데이터가 정렬된 경우에는 항상 이런 최악의 경우가 발생한다.
• 배열이 n/2:n/2로 분할된 경우: nlogn, 가장 균형적인 분할로 피벗이 항상 부분배열의 중간값이 되는 경우.
• 평균: nlogn

피벗 선택의 임의성만 보장되면 평균 성능을 보일 가능성이 매우 높음

합병정렬

전형적인 분할정복 방법이 적용된 정렬 알고리즘

분할: 주어진 배열을 동일한 크기의 두 개의 부분배열로 분할

정복: 각각의 부분배열을 순환적으로 정렬한 후

결합: 정렬된 두 부분배열을 합병하여 하나의 정렬된 배열을 만듦

배열의 원소가 1개만 남을 때 까지 분할 후 합병하며 정렬

Merge() 수행 시간

• 최악 O(n), 전혀 정렬되지 않은 경우
• 최선 O(logn), 정렬되어 있는 경우

합병정렬은 입력 데이터 개수 n만큼의 추가 저장 장소가 필요하다

→ 제자리 정렬 알고리즘이 아님

합병정렬의 수행시간 → 2T(n/2) + O(n) ⇒ O(nlogn)

비순환적 합병정렬도 설계가 가능하다

선택문제

→ n개의 원소가 임의의 순서로 저장된 배열 A에서 i번째로 작은 원소를 찾는 문제

• 직관적인 방법: 정렬 후 i번째 원소 찾기 → nlogn
• 최솟값을 찾는 과정을 i번 반복 → i*n → n^2

선택문제 알고리즘

• 1번 : 최악 O(n^2), 평균 O(n)
• 2번 : 최악 O(n), 평균 O(n)

최솟값 찾기

n개의 데이터에 대해 n-1번의 데이터 비교가 필요 → O(n)

방법1: 최솟값 찾은 후 최댓값 찾기(or 최댓값 찾은 후 최솟값 찾기)

→ n-1 + n-2번 비교 필요

방법2: 모든 원소를 두 개씩 짝을 이루어 동시에 최솟값/최댓값과 비교

선택문제 - 1번

• 퀵 정렬의 분할 함수 Partition()을 순환적으로 적용하는 방법
• 피벗 인덱스의 인덱스가 내가 찾고싶은 i인지 비교해가며 수행

최악 O(n^2), 평균O(n)

분할: 피벗을 기준으로 주어진 배열을 두 부분배열로 분할하고, i가 피벗의 인덱스 p와 같으면 피벗의 값을 반환하고 종료

정복: 인덱스 i가 포함된 부분배열에 대해서 알고리즘을 순환적으로 호출하여 적용

결합: 필요 없음

퀵정렬의 파티션을 응용했으므로 최악의 상황 역시 퀵정렬과 동일하게 정렬되있는 경우 최댓값(최솟값)을 찾을때 발생

선택문제 - 2번

선택문제 -1번 에서 항상 일정한 두 부분배열로 분할되도록 특정 성질을 만족하는 값을 피벗으로 선택

1. 크기 n인 배열의 원소를 5개씩 묶어서 floor(n/5)개의 그룹을 만듦
2. 각 그룹에 대해서 중간값을 찾음
3. floor(n/5)개의 중간값을 대상으로 다시 중간값을 찾음 → 중각값들의 중간값 → 피벗

이때 행의 수가 5개인 2차원 그리드 형태로 부분배열을 나타낼 수 있고,

피벗의 좌상단 값을은 항상 피벗보다 작고, 우하단 값을은 항상 피벗보다 크다

→ 찾고자 하는 수의 인덱스가 피벗보다 큰 경우 좌상단 값들을 다음 탐색에서 제외하고, 피벗보다 작은 경우 우하단 값을을 다음 탐색에서 제외한다.