When to use get MST of undirected & weighted Graph Idea maintain two sets of vertices (1: MST, 2: not visited) find cut vertex minimum weight in each loop until all vertices be included in MST 📝 cut vertex: connect vertex which connects two disjoint subsets Algorithm (1) Create key-value table (vertex - weight) , empty MST Set (2) initialize first value of key as '0' to visit first, remain key a..
greedy
🔒 문제 💭 생각의 흐름 MST (Minimum Spanning Tree) + Undirected Graph => 2가지 방법! Kruskcal Prim✔️ mstSet: 방문된 MST 원소의 집합 not visited Set: 아직 방문하지 않은 노드 번호 - 비용 집합 find minimum cut vertex : mstSet과 not visited Set을 최소 비용으로 연결하는 노드 찾기 mstSet -> 어차피 weight의 총합을 구하는 것이므로 방문 순서를 저장할 필요가 없겠다 -> unorderd_set not visited Set -> 배열로 생성시 따로 visited Boolean 배열이 필요하므로 map 자료구조 사용 ⭐ find minimum cut vertex -> not vist..
1. 문제 2. 아이디어 0. 이 문제의 답은(전체 학생수 - 잃어버린 학생수)로 구하자. -> lost 배열의 원소를 제거하는 방식으로 풀어가자. 1. 도난당한애 == 여벌있는애 일 경우부터 삭제하고 시작하자. ∵ 어차피 여벌있으면서 도난당한애는 다른애한테 빌려주지 못한다. 2. 앞번호 먼저 검사 뒷번호 후검사를 하자. // Mistake 3. 주의사항 for(index in lostList.indices) { // 잃어버린 애, 가져온애가 같으면 양쪽 리스트에서 둘다 삭제 if (reserveList.remove(lostList[index])) lostList.removeAt(index) } for loop에서 index를 활용하여 '정순'으로 순환하면서 컬렉션의 원소를 제거하는 경우 원소가 제거된 ..
