[algo] 분할정복이란?

분할정복이란?

Divide and Conquer
말 그대로
어떤 문제를 해결하는 알고리즘에서 원래 문제를 성질이 똑같은 여러 개의 부분 문제로 나누어 해결하여 원래 문제의 해를 구하는 방식.

순환적으로 문제를 푸는 하향식 접근 방법
주어진 문제의 입력을 더이상 나눌 수 없을 때 까지 순환적으로 분할
분할된 작은 문제들을 각각 해결한 후 그 해를 결합하여 원래 문제의 해를 구하는 방식

분할 정복의 절차
1. Divide
2개 이상의 작은 문제들로 쪼갠다.
2. Conquer
나누어진 작은 문제들을 푼다.
3. Combine
나누어 해결한 문제들을 합친다.

분할정복 알고리즘

1. 이진탐색
2. 합병정렬
3. 퀵정렬
4. 선택 문제

Sources

https://atoz-develop.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B6%84%ED%95%A0%EC%A0%95%EB%B3%B5-%EB%B0%A9%EB%B2%95-%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-%ED%80%B5-%EC%A0%95%EB%A0%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
https://jjunsss.tistory.com/69?category=897276

https://seungjuitmemo.tistory.com/21