분할 정복
분할 정복
분할 정복은 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘이다. 하향식 접근법으로, 상위의 해답을 구하기 위해, 아래로 내려가면서 하위의 해답을 구하는 방식이다. 일반적으로 재귀함수로 구현되며 문제를 잘게 쪼갤 때, 부분 문제는 서로 중복되지 않는다.
분할정복 기본틀
function F(x):
if F(x)의 문제가 간단 then:
return F(x)을 직접 계산한 값
else:
x를 y1, y2로 분할
F(y1)과 F(y2)를 호출
return F(y1), F(y2)로부터 F(x)를 구한 값분할 정복의 설계전략
- 문제 사례를 하나 이상의 작은 사례로 분할(Divide)한다.
- 작은 사례들을 각각 정복(Conquer)한다. 작은 사례가 충분히 작지 않은 이상 재귀를 사용한다.
- 필요하다면, 작은 사례에 대한 해답을 통한(Combine)하여 원래 사례의 해답을 구한다.
분할 정복의 장점
- 문제를 나눔으로써 어려운 문제를 해결할 수 있따는 엄청나게 중요한 장점이 있다. 그리고 이 방식이 그대로 사용되는 효율적인 알고리즘들도 여럿 있으며, 문제를 나누어 해결한다는 특징상 병렬적으로 문제를 해결하는 데 큰 강점이 있다.
분할 정복의 단점
- 함수를 재귀적으로 호출한다는 점에서 함수 호출로 인한 오버헤드가 발생하며, 스택에 다양한 데이터를 보관하고 있어야 하므로 스택 오버플로우가 발생하거나 과도한 메모리 사용을 하게되는 단점이 있다.
Merge Sort(병합정렬)
- 나누어지는 문제의 개수: 2
- 분할 후 문제의 크기: N/2
- 각 문제마다 병합(정복) 단계에서 걸리는 시간: O(N)
k - 1단계에서는 2^(k - 1)번, 2단계에서는 2^2=4번, 1단계에서는 2번, 0단계에서는 1번의 병합을 해야 하는데 각 병합에 걸리는 시간이 해당 문제 크기가 N일때 O(N)이다.
그러므로 각 단계별로 드는 연산 횟수를 죽 늘어놓았을 때
- 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)이라는 시간복잡도를 구할 수 있다.
분할 정복 관련 백준 문제 Github 링크
백준 분할 정복 관련 문제
: )