[CS기초] 분할 정복(Divide and Conquer)

분할 정복 (Divide and Conquer) 개요

분할 정복은 문제를 더 작은 하위 문제로 나누고 각각을 해결한 뒤 결과를 합쳐 원래 문제를 해결하는 알고리즘인데요. 문제를 자연스럽게 나눌 수 있거나, 하위 문제 간의 중복 계산이 없는 복잡한 문제를 효율적으로 해결하는 데 자주 사용됩니다.

 

 

분할 정복의 3단계

분할 (Divide)

• 해결할 문제를 동일하거나 유사한 형태의 더 작은 하위 문제(Subproblem)로 나누는 과정
• 하위 문제는 원래 문제보다 크기가 작아야 하며, 더 이상 나눌 수 없을 때까지 분할해야 한다

정복 (Conquer)

• 나눠진 하위 문제를 개별적으로 해결하는 과정
• 하위 문제의 크기가 충분히 작으면 직접 계산과 같은 직관적인 방식으로 해결한다

결합 (Combine)

• 하위 문제의 해결 결과를 합쳐 원래 문제의 해답을 구하는 과정

 

분할 정복의 특징

재귀적 접근

• 문제를 점점 더 작은 단위로 나누는 과정에서 주로 재귀 함수가 사용된다

점화식을 통한 시간 복잡도 분석

• 분할과 정복 알고리즘은 반복적으로 문제를 나누기 때문에, 대개 점화식으로 시간 복잡도 분석이 가능하다

 

 

분할 정복의 예시

• 합병 정렬 (Merge Sort)
• 퀵 정렬 (Quick Sort)
• 이진 탐색 (Binary Search)

 

 

분할 정복의 장단점

분할 정복의 장점

• 복잡한 문제를 간단하고 체계적으로 해결 가능하다
• 효율적인 알고리즘 설계가 가능하다
• 분할된 하위 문제를 독립적으로 처리할 수 있어 병렬 처리에 적합하다

분할 정복의 단점

• 재귀 호출이 많아지면 스택 오버플로우의 위험이 있다
• 하위 문제의 결합 과정이 비효율적일 경우 성능이 저하될 수 있다