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

(2023-06-13)

분할 후 정복


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

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

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


2. 분할 정복의 주요 특징

  ㅇ 분할된 부 문제들은 서로 독립적임
  ㅇ 소 문제는 원래 문제와 단지 크기 만 작아진 동일한 형태 및 성격을 갖음
  ㅇ 통상, 재귀적인 수행을 수반함  ☞ 재귀 프로그램 참조


3. 분할 정복의 종류

  ㅇ 수평 분할
     - 각각을 수평적으로 구분 할당 
     - 例) 입력, 변환, 출력
  ㅇ 수직 분할
     - 제어와 작업을 위아래로 분리시킴
     - 상위수준에서 제어 기능, 하위수준에 실제 작업 처리 지시


4. 알고리즘 적용 例)

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

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

알고리즘 전략
   1. 알고리즘 설계   2. Brute Force   3. 분할 정복법   4. 탐욕 알고리즘   5. 동적 계획법  
소프트웨어공학 기초
   1. 소프트웨어 공학   2. 버전 관리   3. 요구분석   4. 소프트웨어 설계   5. 소프트웨어 아키텍처   6. CBD (컴포넌트기반개발)   7. MDA (모델주도형구조)   8. 순기/생명주기   9. 분할 후 정복  


Copyrightⓒ written by 차재복 (Cha Jae Bok)               기술용어해설 후원
"본 웹사이트 내 모든 저작물은 원출처를 밝히는 한 자유롭게 사용(상업화포함) 가능합니다"