Coding StudyRoom

- edge들을 오름차순으로 정렬 후 edge를 기준으로 vertex를 선택하자. >> edge-based approach Pseudo_code Kruskal_MST(input G) --------------------------- Sort Edge set 'E' while NOT solved yet{ select next edge 'e': from sorted list IF cycle check: YES -> remove/pass, NO -> add 'e' // kruskal's algo.에서 중요한 부분 IF stop condition: YES-> stop, NO->repeat. } cycle check?? -> 특별한 자료구조와 동작이 필요 tree들이 여러개 존재하고 그들의 관계성을 보려고 한다...

Prim's Algorithm : node(vertex)-based approach(ranking) Pseudo Code F=empty set // 추가되는 edge 집합 Y=P{v1} // 추가되는 vertex 집합 while NOT solved yet{ 1. select v in V-Y nearest to Y; // seletion 2. feasibility test (cycle?) // 불필요 -> 이미 가지고 있는 노드 집합에서 edge를 만들기 때문에 ADD v to Y. 3. if V == Y, then stop/exit. } // A C program for Prim's Minimum // Spanning Tree (MST) algorithm. The program is // for adja..

cf.) DynamicProgramming은 local-optimal을 만족하면 global-optimal을 보장하여 준다. (수학적 모델링 방법 -> recursive equation) greedy는 local-optimal을 만족하면 global-optimal(final)을 보장할 것이라고 가정한다. Grabs data items in sequence, each time with BEST choice, without thinking Future. --> BEST choice : local optimal choice (직관, 경험에 따라) -->> 각기 다른 답이 많이 나옴. // 풀릴때 까지 반복 while NOT solved yet { Step 1. Selection (local..

문제 : 배낭에 담을 수 있는 무게의 최댓값(15kg)이 정해져 있다. 각각 짐의 가치와 무게가 (4$, 12kg), (2$, 1kg), (10$, 4kg), (1$, 1kg), (2$, 2kg)인 경우 짐들을 배낭에 넣을 때 가치의 합이 최대가 되도록했을 때의 최대 $는? 짐을 쪼갤 수 있는 경우 > 그리디 알고리즘으로 해결 짐을 쪼갤 수 없는 경우 > 다이나믹 프로그래밍으로 해결 #그리디 알고리즘 배낭 문제 def fractional_knapsack(cargo): capacity = 15 #배낭 수용량 pack = [] total_price = 0 #단가 계산 역순 정렬 for c in cargo: pack.append((c[0] / c[1], c[0], c[1])) pack.sort(key=lamb..