1. 분할 정복 알고리즘의 기본 원리

주어진 문제의 입력을 분할하여 문제를 해결하는 방식의 알고리즘

• 분할한 입력에 대해 동일한 알고리즘을 적용하여 해를 계산
  • 부분 문제
• 이들의 해를 취합하여 원래 문제의 해를 얻음
  • 부분 해
• 부분 문제를 더 이상 분할할 수 없을 때까지 분할
  

2. 분할 정복 알고리즘의 분류

• 문제가 2개로 분할되고 부분 문제의 크기가 일정하지 않은 크기로 감소( ex.퀵 정렬
• 문제가 2개로 분할되나, 그 중 1개의 부분 문제는 고려할 필요가 없으며, 부분 문제의 크기가 1/2로 감소
  • ex) 이진탐색
• 문제가 2개로 분할되나, 그 중에 1개의 부분 문제는 고려할 필요가 없으며, 부분 문제의크기가 일정하지 않은 크기로 감소하는 알고리즘
  • ex) 선택 문제 알고리즘
• 부분 문제의 크기가 1, 2개씩 감소하는 알고리즘
  • ex) 삽입 정렬, 피보나치 수의 계산

3. 분할 정복 알고리즘 적용 시 유의점

3.1. 분할 정복 알고리즘이 부적합한 경우

• 입력이 분할될 때마다 분할된 부분 문제의 입력 크기의 합이 분할되기 전의 입력크기보다 커지는 경우
• EX) 피보나치 수
  • F(n) = F(n-1)+F(n-2)로 정의되어 순환호출을 사용하는 것이 자연스러워 보이나, 이 경우의 입력은 1개지만, 사실상 n의 값 자체가 입력크기임
  • 2개의 부분 문제인 F(n-1)과 F(n-2)의 입력크기는 (n-1)+(n-2)로 분할 후 입력 크기가 2배로 증가되는 현상
• 주어진 문제를 분할정복 알고리즘으로 해결하는 경우 주의할 점은 취합(정복)과정
• 입력을 분할만 한다해서 효율적인 알고리즘이 만들어지는 것이 아님
• 기하에 관련된 다수의 문제들에서 사용 가능
  • 기하 문제의 특성상 취합 과정이 문제 해결에 잘 부합되기 때문