[알고리즘] 분할 정복 방법이란. 개요와 성능, 기본 점화식과 폐쇄형

분할정복(divide-and-conquer) 방법에 대해 공부한 내용을 기록에 남기고 싶어 글을 적게 되었다.

 

알고리즘에는 여러가지 방법이 있다.

그 중에서 대표적인 알고리즘의 설계기법 중 하나인 분할 정복 방법이 있는데 

분할(divide) 와 정복(conquer), 그리고 결합(combine)이라 하여 분할 정복 방법이라 한다.

이 분할 정복 방법은 기본적으로 순환 알고리즘 형태를 가진다.

 

분할(divide)은 예를 들어 주어진 문제가 있다하면 그 문제를 여러 개의 작은 문제로 분할한다.

정복(conquer)은 작은 문제들을 순환적으로 분할하며, 더 이상 분할되지 않을 정도로 충분히 분할되었다면 그 문제의 해를 구한다.

결합(combine)은 위 정복된 해, 즉 작은 문제에 대해 정복되어 구해진 해들을 결합하여 원래 풀어야할 문제의 해를 구한다.

 

이 알고리즘 방법이 분할 정복 방법이다.

 

분할 정복 방법을 적용한 탐색 기법에는 아래 리스트와 같은 기법이 있다.

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

먼저 이진 탐색은 크기가 n개인 문제를 크기가 $\frac{n}{2}$ 인 두 개의 작은 문제로 분할하는 방식이다.

단, 두 개의 작은 문제로 분할하는데 그 중 하나의 작은 문제는 처리 대상에서 제외하는 방식이다.

 

합병 정렬은 이진 탐색과 동일하게 크기가 n개인 문제를 크기가 $\frac{n}{2}$인 두 개의 작은 문제로 분할하는 방식이다.

 

퀵 정렬은 크기가 n개인 문제를 일정하지 않은 크기로 두 개의 작은 문제로 분할하는 방식이다.

 

선택 문제는 크기가 n개인 문제를 퀵 정렬과 동일하게 일정하지 않은 크기로 두 개의 작은 문제로 분할하지만 그 중 하나는 처리 대상에서 제외하는 방식이다.

 

이 중에서 중요한 포인트는 이진 탐색의 수행 시간, 합병 정렬의 수행 시간, 퀵 정렬의 수행 시간이라 할 수 있는데,

그 식을 점화식으로 표현하면 아래와 같다.

---

이진 탐색의 수행 시간

$T(n) =\begin{cases} \Theta(1),  & n = 1\\T(\frac{n}{2})+\Theta(1), & n  \geq 2\end{cases}$

 

퀵 정렬의 최악의 수행 시간

$T(n) =\begin{cases} \Theta(1),  & n = 1\\T(n-1)+\Theta(n), & n  \geq 2\end{cases}$

 

합병 정렬의 수행 시간, 퀵 정렬의 최선의 수행 시간

$T(n) =\begin{cases} \Theta(1),  & n = 1\\2T(\frac{n}{2})+\Theta(n), & n  \geq 2\end{cases}$

 

---

 

참고문헌 : 이관용・김진욱, "알고리즘", 한국방송통신대학교출판문화원(2023.1.25), p.30~38