분할 정복(Divide and Conquer)

• 문제를 반으로 쪼개고, 또 다시 반으로 쪼개고 반복..
• 가장 작은 단위까지 쪼갠다.
• 쪼개진 문제들을 해결하면서 원래의 문제까지 다시 합쳐나간다.
• 재귀 호출 사용.
• 일반적 재귀 호출과 다른 점
  • 일반적 재귀 호출 : (한 조각 + 나머지 전체)의 형태로 나눔
  • 분할 정복 : (반 + 반)의 형태로 나눔
• 짝수 개의 문제인 경우 : (반 + 반)으로 나눔.
• 홀수 개의 문제인 경우 : (짝수 개의 문제 + 한 문제)로 일단 나누어 놓고, 짝수 개의 문제를 반으로 나눔.
  • (반에 가까운 짝수 개의 문제 + 반에 가까운 홀수 개의 문제)로 나누면 중복 계산이 많아짐.