분할 정복(Divide And Conquer)란?
복잡한 문제를 해결해야 할때,
그 문제를 가능한 가장 간단한 문제로 쪼개어 해결함으로써 복잡한 문제를 간단하게 해결하는 기법이다.
구조
1. 문제를 하위문제로 나눈다.
하위문제는 바로 해결할 수 있을 정도로 가능한한 간단한 문제여야한다.
* 하위문제로 나누는 방법
(1) 기본단계(가능한 가장 간단한 경우)를 찾는다.
(2) 주어진 문제를 작게 줄여서 기본 단계가 되도록 만드는 법을 찾아낸다.
2. 하위 문제를 해결한다.
하위문제 해결을 재귀적으로 수행함으로써 전체 문제를 해결한다.
3. 하위문제의 해결책들을 결합하여 원래 문제의 해답을 만든다.
활용 사례
병합정렬과 퀵정렬
- 아디트야 바르가바, 『Hello Coding 그림으로 개념을 이해하는 알고리즘』, 김도형, 한빛미디어(2017)
글쓴이쿠스, Qus
직업은 소프트웨어 개발자.
기술로 사회문제를 해결하는 시빅해킹(Civic Hacking)에 관심이 많고,
이것저것 생각나는 것들을 글로 정리하는 것을 좋아합니다.
기술로 사회문제를 해결하는 시빅해킹(Civic Hacking)에 관심이 많고,
이것저것 생각나는 것들을 글로 정리하는 것을 좋아합니다.
'자료구조/알고리즘' 시리즈의 다른 이야기들