# 크루스칼

35개의 포스트

[C++] 어두운 길

한 마을은 N개의 집과 M개의 도로로 구성되어 있습니다. 각 집은 0번부터 N - 1번까지의 번호로 구분됩니다. 모든 도로에는 가로등이 구비되어 있는데, 특정한 도로의 가로등을 하루 동안 켜기 위한 비용은 해당 도로의 길이와 동일합니다. 예를 들어 2번 집과 3번 집

약 8시간 전
·
0개의 댓글

[백준] 6497 : 전력난 (JAVA)

문제 > BOJ 6497 : 전력난 - https://www.acmicpc.net/problem/6497 풀이 전체 가로등 중에서 최소한의 가로등만 켜서 전력을 아껴야하기 때문에, 최소 스패닝트리(MST)를 구해서, 전체 길의 길이 - MST를 구성하는 길의 길이를

2021년 7월 16일
·
0개의 댓글

MST 최소 신장 트리

MST, 크루스칼, 프림, 최소신장트리

2021년 7월 8일
·
0개의 댓글
post-thumbnail

[알고리즘] 백준 1197

백준 1197 & union-find 설명

2021년 6월 6일
·
0개의 댓글

백준 1774번 - 우주신과의 교감

최소 스패닝 트리를 구성하는 문제, 먼저 Edge라는 구조체를 만들어 간선의 양 정점과 거리를 저장할 수 있도록한다우선 순위큐를 사용하고 정점간의 거리를 기준으로 오름차순으로 정렬할것이기 때문에 cmp함수를 작성해준다.크루스칼 알고리즘을 사용할 것이기 때문에 유니온파인

2021년 6월 1일
·
1개의 댓글

MST: Kruskal Algorithm과 Prim Algorithm

팁.1\. 일단 유니온 파인드를 위한 3가지 함수를 만든다. (findUnion, isUnion, union)2\. Kruskal 알고리즘은 cost가 작은 것부터 union이 되지 않은 것이면 추가해나가는 방식이므로 PriorityQueue로 담아놓고 cost를 기준

2021년 5월 16일
·
0개의 댓글
post-thumbnail

[프로그래머스/파이썬] (탐욕법(Greedy)) 섬 연결하기

출처n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다.

2021년 5월 3일
·
0개의 댓글
post-thumbnail

[자료구조]그래프 - 7 (크루스칼 알고리즘의 구현) 자료구조 끝 !!!

크루스칼 알고리즘은 다음과 같다."가중치를 기준으로 간선을 내림차순으로 정렬한 다음 높은 가중치의 간선부터 시작해서 하나씩 그래프에서 제거하는 방식"이전에 구현한 것들을 최대한 활용해보자!!!이를 위해 DFS 구현결과인 다음 파일을 활용하자DLinkedList.h,c

2021년 4월 25일
·
0개의 댓글
post-thumbnail

[알고리즘] 크루스칼 알고리즘 (Kruskal Algorithm)

신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리를 찾는 알고리즘을 '최소 신장 트리 알고리즘'이라고 하는데, 대표적인 최소 신장 트리 알고리즘으로는 크루스칼 알고리즘이 있다.크루스칼 알고리즘을 사용하면 가장 적은 비용으로 모든 노드를 연결할 수 있다. 크루스칼

2021년 4월 23일
·
0개의 댓글

[TIL]Day 138

크루스칼(kruskal) 알고리즘이란 탐욕적인 방법을 이용하여 네트워크의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 것 크루스칼 알고리즘 동작 그래프의 간선들을 가중치의 오름차순으로 정렬한다. 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택한다. 해당 간선을 현재의 최소비용신장트리 집합에 추가한다. 어떻게 사이클을 감지할...

2021년 4월 16일
·
0개의 댓글

[골드4] 1922번 : 네트워크 연결

https://www.acmicpc.net/problem/1922전형적인 최소 비용 유형의 문제로, 따로 응용 필요 없이 크루스칼 알고리즘만을 이용해 답을 구할 수 있었다다만 효율성이 떨어지기 때문에 다음에 풀 때는 효율성을 고려한 풀이로 꼭 풀어야겠다소스 코

2021년 4월 9일
·
0개의 댓글

[Level3] 섬 연결하기

https://programmers.co.kr/learn/courses/30/lessons/42861그래프(트리) + 최소의 비용을 읽고 크루스칼 알고리즘을 떠올려 문제를 해결했다소스 코드

2021년 3월 26일
·
0개의 댓글

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

그리디 알고리즘 - 크루스칼 알고리즘

2021년 3월 19일
·
0개의 댓글

[알고리즘] 프로그래머스 - 섬 연결하기

프로그래머스 - 섬 연결하기처음에는 다익스트라로 풀려고했다가 실패했다. 다익스트라는 한 정점에서 다른 모든 정점들에 대해 최소 비용을 알려주는 것이다. 여기서는 전체 간선이 최소화되어야한다. 프림과 크루스칼 알고리즘 간단 차이프림과 크루스칼 시간 복잡도프림을 이용한 풀

2021년 3월 8일
·
0개의 댓글

[프로그래머스] 섬 연결하기 (Java) (Python)

링크1\. 비용이 최소인 것들 부터 탐색 시작2\. 선이 n-1개가 되면 탐색 종료즉, 비용이 최소인 것들만 n-1개 될 때까지 합하자. 라는 풀이 방법을 세웠다. 왜냐하면 문제에 같은 연결은 두 번 주어지지 않습니다. 또한 순서가 바뀌더라도 같은 연결로 봅니다. 즉

2021년 2월 26일
·
2개의 댓글
post-thumbnail

백준 - 전력난[6497]

백준 - 전력난[6497]

2021년 2월 24일
·
0개의 댓글
post-thumbnail

백준 - 네트워크 연결[1922]

백준 - 네트워크 연결[1922]

2021년 2월 24일
·
0개의 댓글
post-thumbnail

백준 - 최소 스패닝 트리[1197]

백준 - 최소 스패닝 트리[1197]

2021년 2월 24일
·
0개의 댓글
post-thumbnail

[Algorithm] BaekJoon : 1647. 도시 분할 계획 by Python

문제 바로가기 https://www.acmicpc.net/problem/1647동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 그러다가 평화로운 마을에 가게 되었는데, 그곳에서는 알 수 없는 일이 벌어지고 있었다.마을은 N개의 집과 그 집들을 연

2021년 2월 19일
·
0개의 댓글