|
|
|
|
분할과 정복 개념
|
|
■ 분할과 정복 개념
- 어려운 문제를 해결하기
쉬운 일련의 작은 문제로 나누어 해결
- 전체 시스템이 지닌
복잡성에 위압당하지 않고, 한 부분씩 해결하는 전략
- 추상화의 원리와 함께
복잡도를 해결하는 도구
■ 분할과 정복 알고리즘의 2개 부분
- 분할
: 작은 부분 문제를 재귀적으로 해결됨(기초사례 부분
제외)
- 정복
: 부분문제(sub-problem) 풀이로부터 원래문제의 답안구성됨
- 조건 : 부분문제들이
서로 중복되지 않음(disjoint)
-
한번 수행된 작업은 결코 반복 수행되지 않음
- 오류 : 분할을
한다고 했지만 사실상 분할이 안될 경우도 있음
-
예를 들면 퀵 정렬에서 항상 제일 큰(작은) 수를
피봇
|
|
|
