분할 정복(Divide And Conquer)

 

분할 정복

 

 

분할 정복 알고리즘

 

분할 정복 알고리즘이란 말 그대로,

 

1. 분할

 

2. 정복

 

순으로 해결하는 것을 말한다.

 

큰 덩어리의 문제를 분할해서 점점 작은 덩어리로 만들어 간다.

 

그러다가 충분히 분할되서 풀기 쉬워질 정도가 되면,

 

그때부터 하나씩 정복해 나간다.

 

그리고 작은 문제들을 하나씩 합쳐가면서, 큰 문제로 조립해나간다.

 

그렇게 처음 해결하려고 했던 문제까지 올라가서 결과를 도출한다.

 

 

분할 정복은 언제 사용해야 할까?

 

답은 그냥 풀었을 때보다 분할하고 합치면서 풀었을 경우에 월등히 연산속도가 빠른 경우에 사용한다.

 

 

분할 정복 알고리즘 수행시간 계산법

 

1. 나누어지는 문제의 개수

 

2. 분할 후 문제의 크기

 

3. 각 문제마다 병합(정복) 단계에서 걸리는 시간

 

 

만약, 병합 정렬을 예로 들면,

 

1은 2, 2는 N/2, 3은 O(N)이다.

 

분할 후에 역순으로 병합을 해나가면

 

0단계: 1 * O(N)

1단계: 2 * O(N)

2단계: 4 * O(N/4)

...

m단계: 2^m * O(N/(2^m)) = O(N)이 된다.

 

즉, 각 단계에서 드는 총합 연산량은 O(N)이 된다.

 

그리고 단계는 총 O(logN)개 있으므로, O(NlogN)이라는 시간 복잡도가 된다.

 

 

 

Reference

 

https://m.blog.naver.com/kks227/220776241154

분할 정복(Divide and Conquer) (수정: 2016-12-25)