반응형 Algorithm3 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. Dynamic Programming Dynamic Programming input size에 대해 base step optimal substructure 찾기 문제 정의 자신보다 작은 substructure에 대한 값이 memorization되어 있다. n size → base step으로 가는 structure가 존재하는가? 백준 예제 카드 구매하기 11052번: 카드 구매하기 #include #include #include int main() { int i, j, N, *P, *M, tmp; scanf("%d", &N); P = (int*)malloc(sizeof(int)*(N+1)); for(i=1; i 2022. 12. 9. Greedy greedy make the choice that appears best at each moments 주어진 문제를 부분 문제로 쪼갰을 때 부분 문제의 상태에서 선택할 수 있는 최선의 선택을 고름 그 앞까지의 결과와 앞으로의 결과를 고려하지 않은 선택 개략적인 접근 방법 기준에 따른 Sorting ⇒ 기준을 무엇으로 정할 것인가? 가장 앞의 것을 고름 The Fractional Knapsack Problem n개의 item 각각의 item은 weight와 profit이 존재 weight의 합이 W가 넘지 않도록 item을 고를 때, profit의 합이 최대가 되는 item subset? 이때 item을 ratio r만큼 “부분” 가져올 수 있다. greedy approach item들을 “profits .. 2022. 12. 9. 이전 1 다음 728x90
