분할 정복이란?

• 큰 문제를 작은 문제로 나누어 해결하고, 그 결과를 합쳐서 원래 문제를 해결하는 알고리즘 기법

분할 정복의 3단계

1. 분할(Divide)
   • 문제를 같은 형태의 작은 문제로 나눈다.
2. 정복(Conquer)
   • 나누어진 작은 문제를 재귀적으로 해결한다.
3. 결합(Combine)
   • 해결된 작은 문제들의 결과를 결합하여 최종 답을 구한다.

대표적인 예시

• 거듭제곱(빠른 거듭제곱)
  • → 로 나누어 계산
  • 시간 복잡도: O(log N)
• 병합 정렬(Merge Sort)
  • 배열을 절반씩 나누어 각각 정렬 후 합침
  • 시간 복잡도: O(N log N)
• 퀵 정렬(Quick Sort)
  • 기준값(pivot) 기준으로 작은 값과 큰 값으로 나누어 정렬
  • 평균 시간 복잡도: O(N log N)

분할 정복의 장점

• 반복문으로 해결할 때보다 시간 복잡도가 줄어듦
• 큰 문제를 작은 문제로 쪼개서 효율적으로 해결 가능

조건

• 나누어진 작은 문제들의 결과를 조합할 수 있어야 함
• 비슷한 형태로 문제를 나눌 수 있어야 함

관련 문제 (백준)

1629 (곱셈)