분할정복과 점화식의 개념

▶ Divide and Conquer (분할정복)

분할정복이란?

재귀적 구조를 가진 여러 알고리즘에서는 주어진 문제를 풀기 위해 자기 자신을 재귀적으로 여러 번 호출함으로써 연관된 부분 문제를 해결하는 방식을 따르는 경우가 많다. 이런 알고리즘들이 보통 따르는 접근법을 '분할정복'이라고 한다.

 

분할정복의 말 그대로 풀어서 다시 설명하자면, 본 문제를 자신과 유사하지만 크기가 작은 몇 개의 부분 문제로 '분할'하고, 그러한 부분 문제를 다시 하나씩 '정복'하는 방식인 것이다.

 

따라서, 분할정복은 재귀 호출을 하는 각 단계에서 다음의 세 단계를 따른다.

 

① Divide(분할): 현재의 문제를 같은 문제를 다루는 다수의 부분 문제로 분할한다.

② Conquer(정복): 분할된 부분 문제를 재귀적으로 풀어서 정복한다. 직접적인 방법이 더욱 효과적이라면 그렇게 푼다.

③ Combine(결합): 부분 문제들의 해를 결합하여 원래 문제의 해가 되도록 만든다.

 

이러한 분할정복 접근법을 사용하는 알고리즘에는 'merge sort', 'maximum-subarray problem', 'Strassen's algorithm' 등 여러가지가 있는데 각각의 알고리즘에 대한 자세한 내용은 나중에 따로 글로 작성해두도록 하겠다.

 

그럼, 여러 분할정복을 사용한 알고리즘들을 알아보기에 앞서서,

'점화식' 에 대해 짚고 넘어가자.

---

▶ Recurrence (점화식)

점화식은 알고리즘의 수행시간을 일련의 식으로 구조화하여 나타낸 것인데, 이는 분할정복 체계에 유용하게 사용된다.

점화식의 수학적인 정의는 더 작은 입력에 대한 자신의 값으로 함수를 나타내는 방정식 혹은 부등식이다.

 

예를 들어, 아래는 merge sort의 최악의 경우의 수행시간 T(n)을 점화식으로 나타낸 것이다.

이 점화식의 해는 \(T(n)=\Theta(n lgn)\) 이다.

 

즉, 우리는 앞으로 알고리즘들의 pseudo-code 등을 참고하여 점화식을 세우고,

그 점화식의 해를 구할 수 있어야 한다. (점화식의 해를 구한다는 것은, 알고리즘의 점근적 \(\Theta(·)\) 혹은 \(O(·)\) 한계를 구하는 것이다.)

 

그렇다면 우리는 이러한 점화식의 해를 구하는 방법을 알아야 할 것이다.

그럼, 다음 글에서 점화식을 푸는 세 가지 방법에 대해서 알아보자.