오뚝이개발자

Divide and conquer(분할정복)이란? 다음의 세 단계를 거치는 알고리즘이다. Divide : large problem을 small subproblem으로 분할 Conquer : recursive하게 각 subproblem을 푼다 Combine : subproblem의 답을 조합해 large problem의 답을 구한다. D&C 사용 예시 [8,2,6,3,9,1,7,5,4,2,8] 리스트 내에서 최솟값, 최댓값을 찾는 문제는 다음과 같이 풀 수 있다. 먼저 large set을 두 그룹으로 나누고, 나누어진 그룹에서 다시 두 그룹으로 나누고....이러한 과정을 풀기에 아주 단순한 small set이 될 때까지 반복한다. 즉, set의 원소 갯수 n이 2개 이하가 될 때까지 하는 것이다.(분할) ..