분할정복이란?
•
둘 이상의 부분 문제로 나눈 뒤, 각 문제에 대한 답을 재귀 호출을 이용해 계산한다.
•
이를 통해 구한 답으로부터 전체 문제의 답을 계산한다.
•
일반 재귀와 다른 점
◦
문제를 한 조각과 나머지 전체로 나누는 것이 아니다.
◦
거의 같은 크기의 부분 문제로 나눈다.
과정
divide
•
문제를 더 작은 문제로 분할하는 과정이다.
merge
•
각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정이다.
base case
•
더 이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제이다.