algorithm study (11) 썸네일형 리스트형 크루스컬(Kruskal) 알고리즘, 최소 신장 트리(MST), python 크루스컬 알고리즘 이란? 최소 신장 트리(Minimun Spanning Tree)란 사이클이 생기지 않게 모든 정점을 연결하면서, 간선의 가중치의 총합이 최소가 되는 트리를 말한다. 크루스컬 알고리즘은 최소 신장 트리를 구하는 알고리즘이다.간선들을 가중치가 작은 것부터 오름차순으로 정렬한 뒤, 간선을 하나씩 선택한다.선택한 간선의 양 끝 두 정점이 같은 집합에 속하지 않았다면 그 간선을 트리에 포함시킨다. 만약 같은 집합에 속한다면 사이클이 생기기 때문에 포함시키지 않는다.이과정을 모든 정점들이 하나의 집합이 될 때까지 반복하면 된다.최소 신장 트리에서 간선의 개수는 정점의 개수 -1 개 이므로 선택된 간선의 개수가 정점의 개수 - 1 개가 되면 종료한다. 크루스컬 알고리즘을 사용해 최소 신장.. 유니온 파인드 알고리즘, python 유니온 파인드 알고리즘이란? 유니온 파인드 알고리즘이란, 두 집합을 하나로 합치고(union) 두 원소가 같은 집합에 속해있는지 확인하는(find) 알고리즘이다. 유니온 파인드를 구현하기 위해서는 부모노드의 번호를 저장할 parents배열과, 트리의 레벨을 저장할 level 배열이 필요하다.parents배열의 초기값은 자기 자신의 번호이고, level은 0이다. 선택된 노드의 루트노드를 찾는 find 함수와, 두 원소를 하나로 합치는 union 함수가 필요하다.find함수는 재귀를 통해 자신이 속한 트리의 루트노드의 번호를 반환한다.union함수는 합칠 두 원소의 루트노드의 번호를 찾고, 레벨이 더 깊은 트리에 작은 트리를 합친다. union 과정 예를 들어 5개의 원소가 있다. 다음과 같은 .. 다익스트라 알고리즘(최단경로 알고리즘), python 다익스트라 알고리즘이란? 그래프의 어떤 한 정점에서 출발하여 다른 정점까지 갈 수 있는 가장 짧은 경로를 찾는 알고리즘이다. 출발점에서 도착점까지의 가장 짧은 경로를 저장할 배열 d를 만들고,탐색하지 않은 정점 중에서 d값이 가장 작은 정점을 탐색해 d [인접한 정점] 과 d [현재 정점] + (현재 정점에서 인접한 정점까지의 길이) 중 더 짧은 경로를 업데이트해주면 된다. 다익스트라 알고리즘으로 최단경로를 구하는 과정 정점의 개수가 5개이고 간선의 정보가 다음과 같다. 출발도착가중치0140221251310243434 위 그래프에서 0번 정점에서 출발하여 다른 정점으로의 최단경로를 구하려 한다. 먼저 각 정점까지의 최단경로를 저장할 배열 d를 만든다. 초기값은 INF로 설정한다.출발점 정점.. 이전 1 2 다음