[CS]분할 정복(Devide & Conquer)

분할 정복 : Devide & Conquer

• 분할 + 정복 + 결합하는 알고리즘
• 최종해(전체 문제의 해)를 구할 때까지 아래 과정 재귀를 통해 반복
  1. 분할(Devide): 전체 문제를 세부 문제로 분할
  2. 정복(Devide): 세부 문제를 정복(해결)
  3. 결합(Combine): 정복한 작은 해를 조합
  
• 사용
  1. 합병 정렬, 퀵정렬
  2. 이진 탐색
  3. 선택 문제
  4. FFT(고속 푸리에 변환) 등
• [TIPS]
  • Devide를 제대로 수행하면, Conquer 과정은 쉬워진다.
    • Devide를 잘 설계하는 것이 중요
• 분할정복 특징
  • 분할된 작은 문제는 원래 문자와 성격이 동일(입력 크기만 작아짐)
  • 분할된 문제는 서로 독립적(중복 제거X) -> 순환적 분할 및 결과 결합 가능
  • 재귀호출의 장단점과 동일
  • [장점1]: 재귀 방식으로 구현 => 코드가 직관적
  • [장점2]: 분할 특성상 병렬 문제 해결
  • [단점1]: 재귀 함수 호출로 인한 오버헤드
  • [단점2]: 스택에 다량의 데이터가 보관되는 경우 오버플로우가 발생 가능