1. 분할 정복 / 분할 통치 (Divide and Conquer) 전략
ㅇ 기본 생각
- 큰 문제를 보다 작은 문제로 분할하는 것은, 복잡함에 대처하는 좋은 수단임
ㅇ 접근 방식
- 문제를 작은 문제로 나눠 순환적으로 푸는 하향식 접근 방식
. 쪼개진 작은 문제들은 원래 문제와 동일한 성격과 특징을 지님
- 다만, 문제의 해를 구할 때는 상향적으로 구해짐
. 작은 문제를 해결한 해를 결합하여 원래 문제의 해를 구함
- 결국, 각 순환 마다, 분할,정복,결합의 단계를 거침
2. 분할 정복의 주요 특징
ㅇ 분할된 부 문제들은 서로 독립적임
ㅇ 소 문제는 원래 문제와 단지 크기 만 작아진 동일한 형태 및 성격을 갖음
ㅇ 통상, 재귀적인 수행을 수반함 ☞ 재귀 프로그램 참조
3. 분할 정복의 종류
ㅇ 수평 분할
- 각각을 수평적으로 구분 할당
- 例) 입력, 변환, 출력
ㅇ 수직 분할
- 제어와 작업을 위아래로 분리시킴
- 상위수준에서 제어 기능, 하위수준에 실제 작업 처리 지시
4. 알고리즘 적용 例)
ㅇ 例) 이진 탐색, 퀵 정렬, 합병 정렬,
선택 문제(최대값/최소값 찾기, n번째 작은 원소 찾기 문제 등)
ㅇ 例) 선형 시스템 풀기, 함수의 근 찾기, 보간법, 수치 적분 등