분할통치법 (Divide and Conquer)

분할통치법이란?

- 일반적인 알고리즘 설계 기법의 일종

- 원래의 문제를 작은 부문제로 분할하고 각 부문제의 해결을 위임하는 것

다음 3가지 절차를 통해 진행

1. 분할 (Divide)

2. 재귀 (Recur)

3. 통치 (Conquer)

분석

재귀 알고리즘은 일반적으로 점화식을 통해 실행시간을 분석한다.

하지만 점화식을 사용하지 않더라도 논리적 직관으로 실행시간을 유추할 수 있다.

응용

분할통치법의 대표적 예로는 합병정렬과 퀵 정렬이 있다.

이외에도 다양한 분야에서 사용되는 알고리즘 설계 기법이다.