분할 정복 알고리즘 (Divide and Conquer)

해당 블로그의 내용은 학교에서 배운 내용을 개인적으로 정리한 내용이므로, 잘못된 부분이 있을 수도 있습니다. 

분할 정복

문제들을 작은 문제들로 나누어 각 작은 문제들은 해를 구해서 그 해들을 통합

분할 정복은 하향식 접근법

 

분할 정복 과정

1. 분할(Divide)
2. 정복(Conquer)
3. 통합(Combine)      

하향식(Top-down) 접근방법

전체를 먼저 정하고 그 밑의 큰 기능들을 정한 뒤, 그것들을 계속 세분화하여 프로그램을 구조화 시키는 것

• 일반적인 재귀 함수
• 분할정복 알고리즘

 

상향식(Bottom-up) 접근방법

하향식 접근과는 반대로 각각의 기능이나 기술을 먼저 만든 뒤에 그것들을 모아서 전체 프로그램을 완성시켜 가는 것

• 일반적인 반복문(대표적 while문)
• 꼬리 재귀 함수
• 동적 계획법

 

분할 정복 기법 기반 알고리즘들

• 탐색
  • 이진탐색
• 정렬
  • 합병정렬
  • 퀵 정렬