Divide and Conquer   분할 정복, 분할 통치

(2019-12-17)
1. 분할 정복/분할 통치 (Divide and Conquer) 전략

  ㅇ 기본 생각
     - 큰 문제를 보다 작은 문제로 분할하는 것은, 복잡함에 대처하는 좋은 수단임

  ㅇ 접근 방식
     - 문제를 작은 문제로 나눠 순환적으로 푸는 하향식 접근 방식
        . 쪼개진 작은 문제들은 원래 문제와 동일한 성격과 특징을 지님
        . 작은 문제를 해결한 해를 결합하여 원래 문제의 해를 구함
        . 각 순환 마다, 분할,정복,결합의 단계를 거침

  ㅇ 주요 특징
     - 분할된 소 문제들은 서로 독립적임
     - 소 문제는 원래 문제와 단지 크기 만 작아진 동일한 형태임
     - 통상, 재귀적인 수행을 수반함

  ㅇ 例) 이진 탐색, 퀵 정렬, 합병 정렬,
         선택 문제(최대값/최소값 찾기, n번째 작은 원소 찾기 문제 등)

  ㅇ 例) 선형 시스템 풀기, 함수 찾기, 보간법, 수치 적분


[알고리즘 전략] 1. 알고리즘 설계 2. Brute Force 3. 분할 정복법 4. 탐욕 알고리즘

 
        최근수정     요약목록     참고문헌