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

분할정복(Divide and Conquer Algorithm)이란?

• ‘큰 문제’를 ‘작은 문제’로 나누어서 해결하는 알고리즘을 의미한다.
• 해당 알고리즘을 활용하여 크고 방대한 문제를 해결할 때 유용한 알고리즘.
• 구체적으로 하나의 큰 문제를 작은 부분 문제들로 나눈 뒤, 나눈 부분 문제를 해결하고 해결된 해들을 모아 원래의 문제를 해결해 나아가는 방식을 의미한다.
• 분할 → 정복 → 결합 과정의 순서를 갖는다.
• 주로 퀵정렬, 합병정렬, 이진탐색 등에 사용된다.

그림으로 알아보기

분할정복법의 장점

• 문제를 나눔으로써 어려운 문제를 해결할 수 있다.
• 분할 정복 방식이 그대로 사용되는 효율적인 알고리즘들도 존재한다.
• 문제를 나누어 해결한다는 특징상 병렬적으로 문제를 해결하는 데 큰 강점이 있다.

분할정복법의 단점

• 함수를 재귀적으로 호출한다는 점에서 함수 호출로 인한 오버헤드가 발생한다.
• 스택에 다양한 데이터를 보관하고 있어야 하므로 스택 오버플로우가 발생하거나 과도한 메모리 사용을 하게 되는 단점이 있다.