반응형 divide and conquer1 Divide and Conquer Divide and Conquer 크기 N짜리 문제에 대해 top-down 방식으로 하여 "재귀적"으로 문제를 푸는 알고리즘 크기 N짜리 문제를 N보다 크기가 작은 subproblems으로 나눈다 (Divide) subproblems를 기존의 방식으로 풀어낸다(recursive). (Conquer) 이때 subproblems가 크기 N에 대해 "모두" 고려해야한다. Merge Sort N개의 크기를 가지는 array를 nondecreasing하게 정렬하기 크기 N인 array에 대해 N/2 인 subarray로 나누어 문제를 해결 $$ T(n)=2T(\cfrac{n}{2})+cn $$ $T(n)$ : 입력 크기가 $n$인 문제를 해결하는 데에 드는 비용 Base Step 가장 크기가 작은 입력데이터에 대.. 2022. 12. 9. 이전 1 다음 728x90