강의

분할 정복이란? 분할 정복(Divide and Conquer)이란 알고리즘 디자인 패러다임 중 하나로, 주어진 문제를 둘 이상의 부분 문제로 나눈 후, 각 문제에 대한 답을 재귀를 통해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산해내는 알고리즘입니다. 일반적인 재귀와 다른 점 분할 정복은 일반적인 재귀와 다르게 부분 문제를 나눌 때 '거의 같은 크기의 부분 문제'로 나눈다는 점입니다. 반면에 일반적인 재귀는 하나의 조각과 나머지 전체로 나눕니다. 분할 정복의 구성 요소 - 문제를 더 작은 문제로 분할하는 자연스러운 방법 - 각 문제에 대한 답을 원래 문제에 대한 답으로 병합하는 효율적인 방법 + 더이상 분할하지 않고 바로 풀 수 있는 매우 작은 문제