분할 정복법
분할 정복법(Divide and Conquer)은 여러 알고리즘의 기본이 되는 해결방법으로, 기본적으로는 엄청나게 크고 방대한 문제를 조금씩 조금씩 나눠가면서 용이하게 풀 수 있는 문제 단위로 나눈 다음 그것들을 다시 합쳐서 해결하자는 개념에서 출발하였다. 대표적으로는 퀵소트 나 병합정렬이 있다. 그 외에 오토마타에서도 top-down parser등의 개념을 위하여 이용된다.
핵심은 재귀함수를 이용하는데에 있다.
병합정렬이나 퀵소트에서는 조건에 부합하지 않을 시
재귀함수를 호출해 1개의 문제를 2개의 작은 문제로 나눈다
아래 이미지를 참고하자
