1. 분할 정복 / 분할 통치 (Divide and Conquer) 전략
ㅇ 기본 생각
- 큰 문제를 보다 작은 문제로 분할하는 것은, 복잡함에 대처하는 좋은 수단임
ㅇ 접근 방식
- 문제를 작은 문제로 나눠 순환적으로 푸는 하향식 접근 방식
. 쪼개진 작은 문제들은 원래 문제와 동일한 성격과 특징을 지님
- 다만, 문제의 해를 구할 때는 상향적으로 구해짐
. 작은 문제를 해결한 해를 결합하여 원래 문제의 해를 구함
- 결국, 각 순환 마다, 분할,정복,결합의 단계를 거침
. 분할 (divide) : 입력을 여러 작은 문제로 분할
. 정복 (conquer) : 작은 문제들을 순환적으로 분할 정복
. 결합 (combine) : 작은 문제의 정복된 해를 결합하여 원래 문제의 해를 구함
2. 분할 정복의 특징
ㅇ 분할된 부 문제들은 서로 독립적임
ㅇ 부 문제는 원래 문제와 단지 크기 만 작아진 동일한 형태 및 성격을 갖음
ㅇ 통상, 재귀적인 수행을 수반함 ☞ 재귀 프로그램 참조
3. 분할 정복에서, 분할의 종류
ㅇ 수평 분할
- 각각을 수평적으로 구분 할당
- 例) 입력, 변환, 출력
ㅇ 수직 분할
- 제어와 작업을 위아래로 분리시킴
- 상위수준에서 제어 기능, 하위수준에 실제 작업 처리 지시
4. 알고리즘 적용 例)
ㅇ (알고리즘)
- 이진 탐색 (Binary Search)
. 정렬된 배열에서 특정 값을 찾기 위해 검색 범위를 절반으로 줄여가며 탐색
- 퀵 정렬 (Quick Sort)
. 배열을 피벗 기준으로 작은 값과 큰 값으로 나눈 후, 각각을 재귀적으로 정렬
- 병합 정렬
. 배열을 절반으로 나누고, 각각을 재귀적으로 정렬한 후, 두 정렬된 배열을 병합
- 선택 문제 (최대값/최소값 찾기, n번째 작은 원소 찾기 문제 등)
. 퀵 정렬과 비슷한 방식으로, 피벗을 선택하고 이를 기준으로 작은 값과 큰 값으로 나눔
. 찾고자 하는 원소가 포함된 부분만 재귀적으로 탐색하여 효율성을 높임
ㅇ (수치해석)
- 큰 선형 시스템 풀기
. 큰 행렬을 여러 작은 블록으로 나누고, 각 블록을 재귀적 처리하는 블록 행렬 분해 기법
- 함수의 근 찾기
. 이분법이 분할 정복 전략의 전형적인 예로써,
. 구간을 반복적으로 반으로 나누어 함수의 부호 변화가 있는 구간을 찾아 근을 결정
- 수치 적분
. 적분 구간을 여러 작은 구간으로 분할하여 각 구간에서 근사값을 구한 뒤 결과를 합산하는 등