분할 정복

1. 도입

분할 정복은 가장 유명한 알고리즘 디자인 패러다임으로, 이 방식을 차용한 알고리즘들은 주어진 문제를 둥 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산해 낸다. 분할 정복이 일반적인 재귀 호출과 다른 점은 문제를 한 조각과 나머지 전체로 나누는 대신 거의 같은 크기의 부분 문제로 나누는 것이다.
분할 정복을 사용하는 알고리즘들은 세가지 구성 요소를 가지고 있다.

• 문제를 더 작은 문제로 분할하는 과정
• 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정
• 더 이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제

분할 정복의 장점은 많은 경우에서 같은 작업을 더 빠르게 처리해 준다. 같은 문제라도 어떻게 분할하느냐에 따라 시간 복잡도에서 많은 차이를 보일 수 있다. 그렇기 때문에 최대한 절반을 나눌 수 있도록 변경시키면서 하는게 좋을 수 있다. 이것은 알고리즘의 효율에 관련이 있는 얘기이다.