[알고리즘] 크루스칼 알고리즘

정의 Spanning Tree, 최소 비용 신장 트리를 O(ElogV)O(ElogV)만에 구하는 알고리즘이다. 신장 트리의 조건 본래의 그래프의 모든 노드를 포함해야함 모든 노드가 서로 연결 트리의 속성 만족 (사이클 존재하지 않음) 코드 parent = {} rank = {} def find(node): if parent[node] != node: parent[node] = find(parent[node]) return parent[node] def union(node_v, node_u): root1 = find(node_v) root2 = find(node_u) if rank[root1] > rank[root2]: parent[root2] = root1 else: parent[root1] = root..
알고리즘/그리디 2020. 11. 18. 00:20

[알고리즘] 그리디 (탐욕법) 알고리즘

정의 그리디 알고리즘(욕심쟁이 알고리즘, Greedy Algorithm)이란 "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자" 라는 모토를 가지는 알고리즘 설계 기법이다. 단, 그리디 알고리즘을 사용하면 매 선택이 그 순간에 대해서는 최적이지만 그걸 종합적으로 봤을 땐 최적이라는 보장은 절대 없다는 것을 명심해야 한다. 사용되는 예시 AI에 있어서 결정 트리 학습법(Decision Tree Learning) 활동 선택 문제(Activity selection problem) 거스름돈 문제 최소 신장 트리 (Minimum spanning tree) 제약조건이 많은 대부분의 문제 다익스트라 알고리즘 허프만 코드 크러스컬 알고리즘
알고리즘/그리디 2020. 11. 15. 23:05