분할정복(Divide & Conquer)

특정한 문제를 풀이함에 있어 큰 문제를 작은 문제로 나뉘어서 푸는 방법들에 대해서는 앞선 포스트들을 통해 계속해서 언급하였다. 오늘 다룰 분할정복(Divide & Conquer)은 그 패러다임을 가장 직관적으로 다루는 테크닉이라고 볼 수 있다. 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산해내는 것 분할정복은 아래의 세 구성요소로 다시 생각해볼 수 있다. Divide : 문제를 더 작은 문제로 분할하기 Merge : 각 문제의 답을 원래 문제에 대한 답으로 병합 Base Case : 더 이상 분할하지 않고 곧장 풀 수 있는 매우 작은 문제 세 구성요소에 대해서는 부가적인 설명이 필요없을 것으로 보이나, 분할정복으로 특정 문..

원문링크 : 분할정복(Divide & Conquer)