02. 분할 정복

[1. 개요]

주어진 문제를 둘 이상의 부분 문제로 나눈 뒤,

각 문제에 대한 답을 재귀호출을 이용해 계산하고,

각 부분 문제의 답으로부터 전체 문제의 답을 계산

 

여기서 일반적인 재귀 호출과 다른 점은 문제를 한 조각과 나머지 전체로 나누는 것이 아니라

거의 같은 크기의 부분 문제로 나누는 것 (=> 보통 절반씩 나눔 => O(logn))

 

적용을 위해서는 문제에 몇 가지 특성이 성립해야 한다.

• 문제를 둘 이상의 부분 문제로 나누는 자연스러운 방법이 있어야 한다.
  => 어떻게 분할하느냐에 따라 시간 복잡도 차이가 커진다.
  
  
• 부분 문제의 답을 조합해 원래 문제의 답을 계산하는 효율적인 방법이 있어야 한다.

보통 같은 작업을 더 빠르게 처리해 준다.

 

 

[2. 구성 요소]

1. Divide => 문제를 더 작은 문제로 분할
2. Merge => 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합
3. Base case => 더 이상 분할 하지 않고 곧장 풀 수 있는 매우 작은 문제

 

[3. 완전 탐색과 비교]

 

 

 

[3. 예제]

https://testkernelv2.tistory.com/336