[Algorithm] 분할정복(4) - Selection

🤔분할정복

분할정복이란 일반적으로 주어진 문제를 작은 단위로 분할한 뒤 분할된 문제들을 재귀적으로 해결하여 해당 답을 적절하게 조합하여 큰 문제의 답을 제시하는 알고리즘을 말합니다.

 

이때 분할된 문제들을 조합하여 큰 문제를 해결하는 것을 Conquer이라고 합니다.

 

이번 시간에는 Good Pivot을 찾기 위한 Selection 알고리즘에 대해 배워보도록 하겠습니다.

 

Good Pivot을 찾는 것은 MOM(Median Of Medians)를 찾는 것에 필수적인 정보이기 때문에 꼭 제대로 숙지해야합니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

🔎 Selection - Quick Select

 

🤔 Problem

크기가 $n$인 배열 A가 주어졌을 때, A에서 $k$번째로 작은 원소를 찾아야 합니다.

 

 

 

특별히 $k$가 $n/2$ ($n$이 even 인 경우) 혹은 $(n+1)/2$ ($n$이 odd인 경우) 일 때, $k$번째 작은 원소를 A의 median (중앙값) 이라고 합니다.

 

아래의 배열에서 $k = 1$이라면 가장 작은 원소를 찾아야 하므로 1을 반환합니다.

 

하나 더 알아보자면 $k = 9$라면 9번째로 작은 원소를 찾아야 하므로 10을 반환합니다.

 

마지막으로 Median 값은 $k = 10/2 = 5$ 즉, 5번째로 작은 원소인 6을 반환해야 합니다. 

 

 

 

 

 

 

 

 

 

 

🤔 Solution 1

$A$를 정렬하여 $k$를 찾는 방법입니다.

 

 

 

자료구조에서 배운 worst case인 merge sort 또는 heap sort를 이용하여 $k$를 찾으면 $O(nlogn)$시간이 걸립니다.

 

 

 

 

 

 

 

 

 

 

 

🤔 Solution 2

Divide and Conquer 이용하는 방법입니다.

 

이번에 학습할 Quick Select가 Divide and Conquer 알고리즘을 이용한 방법입니다.

 

 

 

 

 

 

 

Worst Case

1), 2), 3)을 차례로 실행하며 $n'$이 $n - 1$일때 worst case로 작동합니다.

 

최종적으로 $O(n^2)$시간에 비례하는 것을 알 수 있습니다.

 

 

 

 

 

아래와 같은 식으로 아무 숫자를 pivot으로 설정합니다.

 

 

 

 

 

 

 

Average case(Expectation)

더 좋은 pivot을 확률적으로 계산하여 뽑을 수 있습니다.

 

해당 방법을 통해 뽑아진 pivot을 "Good Pivot"이라고 합니다.

 

과정은 아래와 같습니다.

 

최종적으로 $O(n)$의 시간에 비례하는 것을 알 수 있습니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

🔎 Selection - Quick Sort

 

더 나아가 Quick Sort에 위의 방법을 적용하면 아래와 같은 결과를 얻을 수 있습니다.

 

 

 

 

 

 

 

 

 

 

 

 

순서는 뒤죽박죽이었지만 지금까지 분할정복에 대해 알아보았습니다.

 

MOM(Median Of Medians)를 이해하기 위해서는 Good Pivot을 설정하는 알고리즘이 매우 중요하므로 꼭 제대로 이해하고 다음 포스트로 넘어가기를 추천합니다.