분할 정복

Divide & Conquer

 

주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산

 

 

일반적인 재귀 호출은 문제를 한 조각과 나머지 전체로 나누는 반면, 분할 정복은 거의 같은 크기의 부분 문제로 나눔.

 

 

세 가지의 구성 요소

• 문제를 더 작은 문제로 분할하는 과정 (Divide)
• 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정 (Merge)
• 더이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제 (Base case)

 

가장 대표격이라 할 수 있는 문제는

6549번: 히스토그램에서 가장 큰 직사각형