분할 정복(Divide and Conquer) 문제를 나눌 수 없을 때 까지 나눠 각각을 풀면서 다시 합병하여 문제를 해결하는 알고리즘이다. 상위의 해답을 구하기 위해 아래로 내려가며 하위의 해를 구하는 하향식 접근법을 사용하여 일반적으로 재귀함수로 구현된다. 분할정복의 대표적인 알고리즘은 퀵 정렬과 병합 정렬이 있다. DP와 분할 정복이 비슷한 느낌이어서 공통점과 차이점을 찾아보았다. 공통점 문제를 가장 작은 단위가 될 때까지 나눠서 분할함 차이점 동적 계획법 중복된 문제의 답은 저장되어 상위 문제 해결 시 재활용 됨 (메모이제이션 기법) 분할 정복 부분 문제는 서로 중복되지 않음(메모이제이션 기법 사용 안함) 분할 정복을 설계하는 방법 1) Divide : 문제가 분할이 가능할 경우, 2개 이상의 문..