[분할과 정복] 개념 정리

분할 정복이란?

여러 알고리즘의 기본이 되는 해결방법으로, 기본적으로는 엄청나게 크고 방대한 문제를 조금씩 조금씩 나눠가면서 용이하게 풀 수 있는 문제 단위로 나눈 다음, 그것들을 다시 합쳐서 해결하자는 개념에서 출발하였다.

대표적으로는 퀵소트나 병합 정렬이 있다.

그림에서와 같이 분할 정복은 상단에서 분할하고 중앙에서 정복하고 하단에서 조합하는 형태로 도식화 할 수 있다.

• 분할 : 문제를 더이상 분할할 수 없을 때까지 동일한 유형의 여러 하위 문제로 나눈다.
• 정복 : 가장 작은 단위의 하위 문제를 해결하여 정복한다.
• 조합 : 하위 문제에 대한 결과를 원래 문제에 대한 결과로 조합한다.

마스터 정리

점화식을 해결하기 위한 일반적인 방법 중 하나로, 분할 정복 알고리즘에서 주로 사용된다.

 

점화식이 특정한 형태일 때, 점화식의 해를 구할 수 있는 일반적인 방법을 제공한다.

 

$$ T(n) = a * T(n/b) + f(n) $$

 

위와 같은 점화식을 해결할 수 있다.

 

여기서 a는 재귀호출의 개수, b는 입력의 크기를 나누는 비율, f(n)은 재귀호출이 아닌 부분에서 수행되는 연산이다. 이러한 점화식의 해를 구하기 위해, 다음과 같은 3가지 조건을 검사한다.

 

 

a >= 1, b >= 2, C > 0이고 만약 f(n)이 d가 0보다 크고 $\theta(n^d) $ 이면

 

 

위와 같은 방식으로 해결하면 점화식의 해를 구할 수 있다.

함정

마스터 정리는 다음과 같이 사용할 수 없다.

• T(n)이 비단조 함수일 때 (ex. T(n) = sin(x))
• f(n)이 다항식이 아닐 때 (ex. T(n)=2T(n/2)+2n)
• b가 상수로서 표현할 수 없을 때 (ex. $T(n) = T(\sqrt{n}))\

• 마스터 정리는 반복 방정식을 풀지 못한다.

분할 정복을 사용하지 않을 경우

1. 크기가 n인 사례가 거의 n에 가까운 두 개 이상의 사례로 분할될 때
   • 이렇게 분할하면 지수 시간 알고리즘이 나온다.
2. 크기가 n인 입력이 거의 n개의 조각으로 분할되며, 분할된 부분의 크기가 n/c인 경우 (여기서 c는 상수)
   • 시간복잡도: nΘ(lg n)

만약 피보나치 수열을 재귀적인 방법 즉, 분할 정복을 이용해서 문제를 해결했다면, 지수시간 알고리즘이 나온다.

왜냐면 n-1, n-2로 또 분할해서 계산하기 때문이다.

이럴때는 분할 정복을 사용하면 안된다. -> 반복문을 이용한다면 1차식이기 때문에

반면에 때로는 지수 시간으로 풀어도 괜찮은 문제들이 있다.

대표적으로 하노이 탑 문제인데 본질적으로 지수시간 알고리즘이다. 이를 intrinsically exponetial algorithm 이라고 한다. 지수 시간 이하로 시간을 줄일 수 없다는 뜻이다.

참고

https://jelong.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B6%84%EC%84%9D-The-Master-Method
https://yejin013.tistory.com/32
https://hi-guten-tag.tistory.com/47