분할정복

분할 정복은 말 그대로 분할과 정복으로 문제를 나누어서 해결하는 것을 말한다. 이 기법이 먹히는 경우는 그냥 풀었을 때보다 이미 풀린 부분문제를 합치는게 월등히 빠른 경우이다.

분할하는 단계에서는 말 그대로 주어진 문제를 여러개의 부분문제로 나누는데, 이 경우 문제가 작아질수록 풀기 쉬워지는 성질을 이용한다.
문제가 작아지다가 엄청 작아져서 N=1 또는 N=2정도로 작아지면 바로 답을 구할 수 있는 수준이 된다. 이것이 재귀로 문제를 풀 때 기저 사례(base case)와 같다.
따라서 분할 정복은 재귀호출과 잘 맞는다고 볼 수 있다.
기저 사례로 각 문제의 답을 풀고 더 큰 문제와 결합하여 쌓아올려가며 답을 풀어내는 것이다.

분할 정복 알고리즘의 수행시간에서 중요한 것은

1. 분할할 때 나누어지는 문제의 개수 a
2. 분할 후 문제의 크기 b
3. 각 문제마다 정복하는 단계에서 걸리는 시간 d

이다. 아래의 사진에 대입하였을 때 시간복잡도를 알아낼 수 있다.