분할정복_DivideAndConquer

분할정복(Divide and Conquer)

• 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방식
• 대표적인 예
  • 퀵정렬
  • 합병정렬
  • 이진탐색
  • 선택문제
  • 고속 푸리에 변환

분할정복의 설계

1. Divide - 원래 문제가 분할하여 비슷한 유형의 더 작은 하위 문제로 분할 가능할때까지 나눈다.
2. Conquer - 각 하위 문제를 재귀적으로 해결한다. 하위 문제의 규모가 나눌 수 없는 단위가 되면 탈출 조건을 설정하고 해결한다.
3. Combine - Conquer한 문제들을 통합하여 원래 문제의 답을 얻어 해결한다.

• Divide를 제대로 나누면 Conquer 과정은 자동으로 쉬워진다. 그래서 Divide를 잘 설계하는 것이 중요하다.
• 분할정복 알고리즘은 재귀 알고리즘이 많이 사용되는데, 이 부분에서 분할정복 알고리즘의 효율성을 깎아 내릴 수 있다.

분할정복 특징 및 장단점

• 분할 된 작은 문제는 원래 문제와 성격이 동일하다 → 입력 크기만 작아짐
• 분할 된 문제는 서로 독립적이다.(중복 제거 X) → 순환적 분할 및 결합 가능
• 장점
  • Top-down 재귀 방식으로 구현하기에 코드가 직관적이다.
  • 문제를 나누어 해결한다는 특징상 병렬적으로 문제 해결이 가능하다.
• 단점
  • 재귀 함수 호출로 오버헤드가 발생할 수 있다.
  • 스택에 다량의 데이터가 보관되는 오버플로우가 발생할 수 있다.