3강 제 2 장 분할정복 알고리즘

학습 목표 

1. 분할 정복 방법의 개념과 원리를 이해할 수 있다.

2. 이진 탐색의 개념, 동작, 그리고 특징을 이해할 수 있다.

3. 합병 정렬과 퀵 정렬의 개념, 동작, 그리고 특징을 이해할 수 있다.

4. 선택 문제의 개념, 동작, 그리고 특징을 이해할 수 있다.

 

주요 용어

#분할정복 방법 #이진탐색 #합병정렬 #합병함수 #퀵정렬 #피벗 #분할함수 #선택문제

 

2.1 분할 정복 방법의 원리

분할정복(divide-and-conquer)방법 :

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

주어진 문제의 입력을 더 이상 나눌 수 없을 때까지 두 개 이상의 작은 문제로 순환적으로 분할하고,

이렇게 분할된 작은 문제들을 각각 해결한 후 그 해를 결합하여 원래 문제의 해를 구하는 방식

 

특징

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

분할된 문제는 서로 독립적 → 단,입력 크기만 작아짐

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

 

 

&원리 : 각 순환 호출 시의 처리 과정

 

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

 

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

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

 

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

 

 

 

2.2 이진 탐색 트리

2.2.1 개념과 원리

 

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

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

 

탐색 방법

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

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

2)탐색키 < 가운데 원소 ⇒ ‘이진 탐색(크기 ½의 왼쪽 부분배열)’순환 호출

3)탐색키 > 가운데 원소 ⇒ ‘이진 탐색(크기 ½의 오른쪽 부분배열)’순환 호출

 

개념과 원리

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

 

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

 

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

 

 

 

 

 

2.2.2 알고리즘 

이진탐색 ( 순환 형태의 알고리즘 )

이진 탐색 ( 반복 형태의 알고리즘 )

 

 

 

2.2.3 성능 분석

T(n)=입력 크기 n에 대한 탐색 과정에서의 모든 비교 횟수의 합

=맨 바깥 수준에서의 비교 횟수 + 순환 호출에서의 비교 횟수

 

T(n) = T(n/2) + O(1) (n > 1), T(1) = 1

T(n) = logn

Θ(logn)

 

2.2.4 특징

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

 

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

평균 n/2개의 데이터 이동이 발생

→ 삽입/삭제가 빈번한 응용에는 부적합

 

 

 

 

2.3 퀵 정렬

2.3.1 개념과 원리

 

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

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

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

 

피벗 pivot

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

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

 

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

 

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

 

결합 : 필요 없음

 

 

 

2.4.2 알고리즘 

퀵 정렬 (순환 호출)

 

 

퀵 정렬 (분할 함수 )

 

 

 

2.4.3 성능 분석

 

퀵 정렬 QuickSort()수행 시간

한 번의 분할 Partition() +두 번의 QuickSort()순환 호출

 

성능 분석_최악의 경우

극심한 불균형적 분할

 

피벗만 제자리를 잡고,나머지 모든 원소가 하나의 부분배열이 되는 경우

피벗이 항상 부분배열의 최솟값 또는 최댓값이 되는 경우

입력 데이터가 정렬된 경우 AND 피벗을 배열의 처음 원소로 지정한 경우

T(n)=T(n-1)+T(0)+Θ(n)(n>0),T(0)=0

T(n)=T(n-1)+Θ(n)

T(n)=O(n2)

 

 

성능 분석_최선의 경우

가장 균형적인 분할

피벗을 중심으로 항상 동일한 크기의 두 부분배열로 분할되는 경우 가장 균형적인 분할

피벗이 항상 부분배열의 중간값이 되는 경우

T(n)=T(n/2(하한))+T(n/2(하한))+Θ(n) (n>1) T(1)=1

T(n)=2T(n/2)+Θ(n)

T(n)=O(nlogn)

 

성능 분석_평균적인 경우

부분배열의 모든 분할 비율에 따른 수행 시간의 평균

피벗은 동일한 확률로서 분할 후 배열의 어느 곳에나 위치 가능

• 0:n-1,1:n-2,2:n-3,…,n-2:1,n-1:0

 

T(n)=O( nlogn )

 

 

 

2.4.4 특징

 성능 : T(n)=T(n/2)+Θ(1), T(1)=Θ(1) → Θ(logn) 성능 : T(n)=T(n/2)+Θ(1), T(1)=Θ(1) → Θ(logn)

 

최선/평균의 경우 → O(nlogn)

최악의 경우 → O(n2)

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

• 배열에서 임의로 값을 선택해서 배열의 처음 원소와 서로 교환한 후 정렬 수행

 

1강 제 1강 알고리즘 1.3 알고리즘 설계

1강 제 1강 알고리즘 1.3 알고리즘 설계

 

4강 제2장 분할정복 알고리즘 2

4강 제2장 분할정복 알고리즘 2