분할 정복

 

분할 정복 (Divide and Conquer)

• 큰 문제를 작은 문제로 나누어서 해결하는 알고리즘
• 분할 > 정복 > 결합 과정으로 진행

 

분할 정복 장점

• 문제 해결 과정 간편
• 빠른 속도
• 대규모 문제 해결 용이

 

분할 정복 단점

• 스택 오버 플로우 문제 발생 가능성
• 추가적인 메모리 필요 가능성
• 분할된 문제가 같은 크기를 갖지 않은 경우 효율성 다운

 

일반적으로 O(nlogn) 정도는 시간 복잡도를 가짐

 

예시

• 퀵정렬 : 피벗 값을 이용하여 정렬 하는 방식
• 이진검색  : 정렬된 정수 배열에서 특정 값을 찾는 함수 
• 병합 정렬 : 리스트의 길이가 0또는 1이 될때 까지 분할 그후 합치며 전체 정렬 하는 방식