Divide and Conquer (분할정복)에 대해 설명하세요
Keyword
전체문제, 서브문제, 독립적
Script
분할정복은 전체 문제를 서브 문제들로 나누어서 문제를 해결하고 이를 합쳐 전체 문제를 해결하는 전략입니다. 분할정복 기법을 적용하기 위해서는 몇가지 조건이 필요합니다.
먼저, 큰 문제와 작은 문제의 구조가 동일해야 합니다. 즉, 큰 문제를 작은 문제로 쪼개도 푸는 해법은 동일해야 합니다.
그리고 각각의 서브 문제들은 서로 독립적이어야 합니다. 만약 서로 영향을 주는 관계가 존재한다면, 분할 정복으로 풀 수 없습니다. 그래서 분할 정복으로 푸는 문제는 같은 입력이 들어온다면 항상 같은 결과를 내는 문제입니다. 즉, 모든 문제들은 독립적입니다.
분할 정복의 예시로는 merge sort, binary search 등이 있습니다.
Additional
with programming