# kruskal

65개의 포스트

Union-Find 알고리즘 최적화

Path Compression and Union by Rank

2022년 7월 13일
·
0개의 댓글
·

[snippet] kruskal.py

백준 1197번. 최소 스패닝 트리에 대한 풀이를 Kruskal's Algorithm의 스니펫 느낌으로 작성.

2022년 7월 12일
·
0개의 댓글
·
post-thumbnail

백준 #1197 최소 스패닝 트리 (파이썬) : 크루스칼 알고리즘

드디어 최소 스패닝 트리를 배웠다. 이번 글에서는 가장 대중적인 방식인 Kruskal Algorithm을 활용한다.

2022년 6월 25일
·
0개의 댓글
·
post-thumbnail

[백준] 2887번 행성 터널 (Java)

문제 링크N의 범위가 최대 100,000 이므로 모든 행성간의 간선 정보를 이중 for문으로 계산할 시 최대 100,000,000,000번을 수행하기 때문에 시간초과가 발생하므로 간선의 정보를 구하는게 문제의 핵심이였다.간선의 가중치를 구하는 순서는먼저 각 행성의 좌표

2022년 6월 12일
·
0개의 댓글
·
post-thumbnail

[백준] 6497번 전력난 (Java)

문제 링크방향성이 없는 간선들 중 최소 비용을 선택해 최소 신장 트리를 만들면 전체 집을 연결하는데 들어가는 최소 비용을 구할 수 있으므로, 기존 최대 액수에서 최소 비용을 빼면 절약할 수 있는 최대 액수를 구할 수 있다. 이번 문제에서는 유니온 파인드를 사용한 크루스

2022년 6월 3일
·
0개의 댓글
·
post-thumbnail

[알고리즘] 크루스칼(Kruskal) 알고리즘. c언어 구현

Kruskal 알고리즘 > 탐욕(Greedy) 알고리즘의 한 종류로 그래프의 있는 모든 정점을 최소 비용으로 연결할 때 사용한다. 그래프 : 정점(node 혹은 vertex)과 간선(edge)으로 이루어져있으며 각 간선에는 가중치(weight)가 부여된다. > 결론

2022년 5월 31일
·
0개의 댓글
·
post-thumbnail

<Baekjoon> #17472_MST, Kruskal, brute force, graph 다리 만들기2 c++

\[최소 비용으로 모든 다리를 연결한다는 점에서 kruskal algorithm 을 떠올린다 각 섬에 번호를 매기고 vec 이라는 이름의 vector를 만들어 {dist, 섬1, 섬2} 를 저장한다. 이는 섬1과 섬2간 거리는 dist라는 뜻이다vec에 저장된 값을 참

2022년 5월 12일
·
0개의 댓글
·
post-thumbnail

[알고리즘] 최소 신장 트리(MST)

신장트리, 최소 신장 트리, kruskal, prim

2022년 4월 5일
·
0개의 댓글
·

SWEA 1251 하나로

각 섬까지의 해저 터널을 만드는데 모든 섬을 연결하면서 그 해저터널의 길이가 최소가 되게끔 하는 문제.전형적인 그래프의 최소 비용 문제그래프 최소 비용 문제를 풀 때 정보를 사용하기 위한 밑 작업으로 infos 배열을 만들어 놓습니다.infos의 요소는 다음과 같은 형

2022년 4월 5일
·
0개의 댓글
·
post-thumbnail

[알고리즘 개념] 최소신장트리(MST)-Kruskal

개념탐욕적인 방법으로 최소신장트리를 구한다순서간선들의 가중치를 오름차순으로 정렬한다정렬된 간선들의 리스트에서 사이클을 형성하지 않는 간선을 찾아 현재의 최소비용 신장트리의 집합에 추가한다실제로 사이클을 알기 위해서는 연결하려는 간선의 양 끝점이 동일한 집합에 없는지를

2022년 3월 31일
·
0개의 댓글
·
post-thumbnail

스패닝 트리 알고리즘

스패닝 트리(Spanning Tree)란? 그래프 내의 모든 정점을 포함하지만 사이클이 없는 트리로, 신장 트리라고도 한다. 스패닝 트리는 그래프의 최소 연결 부분 그래프이다. 최소 연결은 간선의 수가 가장 적은 것을 의미한다. n개의 정점을 가지는 그

2022년 3월 20일
·
0개의 댓글
·

[프로그래머스] 섬 연결하기

https&#x3A;//programmers.co.kr/learn/courses/30/lessons/42861이 문제는 그리디 알고리즘의 일종인 크루스칼 알고리즘으로 풀었다.크루스칼 알고리즘은 전에도 적었지만 가중치가 최소인 최소 스패닝 트리를 구할 때 사용하는 알고리

2022년 3월 17일
·
0개의 댓글
·
post-thumbnail

<Programmers> Greedy_섬 연결하기 + MST, Kruskal Algorithm c++

참고 Kruskal Minimum Spanning Tree Algorithm 모든 간선을 가중치의 오름차순으로 정렬 스패닝 트리에 하나씩 추가 가중치가 작다고 무조건 간선을 트리에 더하는 것이 아니라, 사이클이 생기지 않는 경우에만 트리에 더해준다 상호 배타적 집합

2022년 3월 14일
·
0개의 댓글
·

[백준] 17472번 다리 만들기 2 (C++, 삼성 기출)

https://www.acmicpc.net/problem/17472 이 문제도 크루스칼 알고리즘을 공부하기 위해 풀었다. 섬을 구분하기 위해 bfs를 통해 섬 번호를 넣어줬고, 섬에서 이동하며 간선을 구해 vector에 넣어줬다. 크루스칼 알고리즘을 통해 최소 스패닝

2022년 3월 10일
·
0개의 댓글
·

[백준] 1197번 최소 스패닝 트리 (C++)

https&#x3A;//www.acmicpc.net/problem/1197이번 문제는 크루스칼 알고리즘을 공부하면서 푼 문제이다.크루스칼 알고리즘은 최소 스패닝 트리 즉, 스패닝 트리 중 가중치의 합이 최소인 트리를 구해주는 알고리즘이다.따로 어려운 건 없었고, 크루스

2022년 3월 10일
·
0개의 댓글
·
post-thumbnail

[Python] 백준 1647 - 도시 분할 계획 문제 풀이

분류: Minimum Spanning Tree (최소 스패닝 트리)

2022년 3월 3일
·
0개의 댓글
·

Graph Algorithm - MST

신장의 의미

2022년 3월 2일
·
0개의 댓글
·
post-thumbnail

그래프, MST, Kruskal 알고리즘

관련문제 백준#1922 - 네트워크 연결 크루스컬 적용 후 DFS 로 해결 시도 -> 시간초과로 Union Find 공부해 적용.

2022년 2월 22일
·
0개의 댓글
·
post-thumbnail

Kruskal Algorithm(최소 신장 트리 | MST)

크루스칼 알고리즘은 너무 쉬워

2022년 2월 3일
·
0개의 댓글
·