분할 정복?

문제를 즉각 해결할 수 있을 때까지 재귀적으로 둘 이상의 하위 문제(Sub-problem)들로 나누고(Divide) 문제를 해결한 다음(Conquer) 그 결과를 이용해 다시 전체 문제를 해결하며 합치는 방법이다.
Quick Sort, Merge Sort, 이진탐색 등의 문제가 대표적이다.

분할 정복 과정

1. 문제 사례를 하나 이상의 작은 사례로 분할(Divide)한다.
2. 작은 사례들을 각각 정복(Conquer)한다. 작은 사례가 충분히 작지 않은 이상 재귀를 사용한다.
3. 필요하다면, 작은 사례에 대한 해답을 통합(Combine)하여 원래 사례의 해답을 구한다.

분할 정복의 장점/단점

장점👍

• 문제를 나누어 처리하여 어려운 문제 해결 가능.
• 병렬적으로 문제를 처리한다.

단점👎

• 재귀 호출 구조로 메모리를 많이 사용한다 -> 스택오버플로우 발생 가능

예제

public int total_sum(start, end){
	if(start == end) {
    return start;
  	}
    int mid = start + (end - start) / 2;
    
    return total_sum(start, mid) + total_sum(mid + 1, end);
}

0단계: 1 O(N)
1단계: 2 O(N / 2)
2단계: 4 O(N / 4)
m단계: 2^m O(N / (2^m)) = O(N)

단계별 식을 일반화해 보면 각 단계에서 드는 총합 연산량은 O(N)이다. 이는 매 단계마다 각 문제의 크기 역시 지수적으로 줄어들기 때문이다.
각 단계는 총 O(logN)개 있으므로, 이를 곱해서 O(NlogN) 이라는 시간복잡도를 구할 수 있다.