python185 [코딩 + 알고리즘 완주반] 23일차. 최소 신장 트리 - 프림 알고리즘 (Prim's algorithm) # 프림 알고리즘 시작 정점을 선택한 후, 정점에 인접한 간선 중 최소 간선으로 연결된 정점을 택하고, 해당 정점에서 다시 최소 간선으로 연결된 정점을 선택하는 방식으로 최소 신장 트리를 확장해가는 방법 ( 크루스칼 알고리즘은 전체에서 가장 작은 간선) 1. 임의의 정점을 선택하여 연결된 노드 집합에 삽입 2. 선택한 정점에 연결된 간선들을 간선 리스트에 삽입 3. 간선 리스트에서 최소 가중치를 가지는 간선부터 추출해서 ( 전에 넣었던 간선들 포함 간선리스트에서 가장 최소인 값 ) - 해당 간선에 연결된 인접 정점이 '연결된 노드 집합에 이미 있다면 skip (cycle 방지) - 해당 간선에 연결된 인접 정점이 '연결된 노드 집합에 있지 않다면 해당 간선을 선택 ( 최소신장트리에 삽입 ) (해당 간선에.. 2021. 4. 13. ❗️[LEET CODE] 207. Course Schedule # Problem There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai. For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1. Return true if you can finish all courses. Otherwise, .. 2021. 4. 10. ❗️[LEET CODE] 332. Reconstruct Itinerary # Problem You are given a list of airline tickets where tickets[i] = [fromi, toi] represent the departure and the arrival airports of one flight. Reconstruct the itinerary in order and return it. All of the tickets belong to a man who departs from "JFK", thus, the itinerary must begin with "JFK". If there are multiple valid itineraries, you should return the itinerary that has the smallest lexic.. 2021. 4. 10. [LEET CODE] 78. Subsets # Problem Given an integer array nums of unique elements, return all possible subsets (the power set). The solution set must not contain duplicate subsets. Return the solution in any order. Constraints: 1 2021. 4. 9. [LEET CODE] 39. Combination Sum # Problem Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order. The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.. 2021. 4. 9. [코딩 + 알고리즘 완주반] 22일차. 최소 신장 트리 # 신장 트리 (Spanning Tree) 그래프의 모든 노드가 연결되어 있으면서 트리의 속성을 만족하는 그래프 모든 노드 포함, 모든 노드 서로 연결, 사이클 존재하지 않음 # 최소 신장 트리 (Minimum Spanning Tree, MST) 가능한 신장 트리 중에서 간선의 가중치 합이 최소인 Spanning Tree Kruskal's algorithm(크루스칼 알고리즘), Prim's algorithm(프림 알고리즘) # Kruskal's algorithm(크루스칼 알고리즘) 가중치가 가장 작은 간선부터 연결 ( 사이클일 경우 넘어감 ) # Union-Find 알고리즘 - 사이클이 생기는지 확인하는 알고리즘 Disjoint Set을 표현할 때 사용하는 알고리즘으로 트리 구조를 활용하는 알고리즘 Di.. 2021. 4. 9. 이전 1 ··· 20 21 22 23 24 25 26 ··· 31 다음 반응형
