분할 정복 (Divide & Conquer)

분할 정복

• 분할 정복 패러다임을 차용한 알고리즘들은 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산, 각 부분 문제의 답으로 부터 전체 문제의 답을 계산
• 일반적인 재귀 호출과 다른 점은 문제를 한 조각과 나머지 전체로 나누는 대신 거의 같은 크기의 부분 문제로 나눔
• 일반 재귀 호출은 항상 문제를 한 조각과 나머지로 쪼개는 방식
• 분할 정복법은 항상 문제를 절반씩 나누는 분할 정복 알고리즘

구성 요소

• 문제를 더 작은 문제로 분할 (Divide)
• 각 문제에 대한 구한 답을 원래 문제에 대한 답으로 병합 (Merge)
• 더 이상 답을 분할하지 않고 바로 풀 수 있는 매우 작은 문제 (Base Case)

특성

• 문제를 둘 이상의 부분으로 나누는 자연스러운 방법이 있어야 함
• 부분 문제의 답을 조합해 원래 문제의 답을 계산하는 효율적인 방법이 있어야 함

장점

• 같은 작업을 더 빠르게 처리