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