# 크루스칼

25개의 포스트

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

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

5일 전
·
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일
·
0개의 댓글
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개의 댓글
post-thumbnail

[BOJ] 17472 - 다리만들기 2

BFS와 크루스칼을 이용해서 풀어봅쉬당

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

그래프 알고리즘

👏 그래프란? 노드와 노드 사이에 연결된 간선의 저보를 가지고 있는 자료구조 > 문제에서 서로 다른 개체(혹은 객체)가 연결 되어 있다 라는 말이 있다면 그래프 알고리즘을 떠올려야 한다.

2021년 1월 22일
·
0개의 댓글

[BOJ] 1647 - 도시 분할 계획

그래프에서 최소 신장트리 두개 구하기

2021년 1월 19일
·
0개의 댓글
post-thumbnail

[알고리즘] 신장트리와 크루스칼 알고리즘

신장트리와 크루스칼 알고리즘에 대해 알아보았다 .

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

최소 스패닝 트리 :MST

스패닝 트리 : 원개 그래프의 정점 전부와 간선의 부분 집합으로 구성된 부분 그래프단, 사이클을 이루지 않는다 트리형식이라고 많이들 이야기하지만, 트리의 사이클이 없는 특징을 의미하는 것으로 혼돈하지 말자 스패닝 트리는 유일하지 않다. 방법 1 ) 그래프의 모든

2021년 1월 13일
·
0개의 댓글

섬 연결하기(★★★ / OO / 2) - Python / Javascript

풀이 시간 : 30분시간 제한 : ?메모리 제한 : ?기출 : 프로그래머스 Level 3 문제링크 : https://programmers.co.kr/learn/courses/30/lessons/42861n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어

2020년 12월 15일
·
0개의 댓글

알고리즘 - 기타 그래프

그래프란 노드와 노드 사이에 연결된 간선의 정보를 가지고 있는 자료구조를 의미합니다.알고리즘 문제를 접했을 때 '서로 다른 개체'가 연결되어 있다는 이야기를 들으면 가장 먼저 그래프 알고리즘을 떠올려야 합니다.분리 집합이란 중복 포함된 원소가 없는 집합입니다.분리 집합

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

이것이 코딩 테스트다 :: Part2 :: Chapter 10 :: 그래프 기본 이론

Chapter 10 Section1:: 서로소 집합(disjoint sets) 개념 서로소 집합은 중복되는 원소나 교집합이 없게끔 자료를 저장하는 자료구조를 의미한다. 그래프와 연관되는 개념이지만 서로소 집합은 트리 개념(Root-Parent-Child)을 따르는 것이

2020년 9월 28일
·
0개의 댓글

그래프 알고리즘

최단경로 [다익스트라], 최소신장 트리[크루스칼, 프림] + union/find 정리

2020년 9월 4일
·
0개의 댓글
post-thumbnail

[알고리즘] 최소 신장 트리

1) 최소 신장트리의 이해 신장트리란? Spanning Tree, 또는 신장 트리 라고 불리움 원래의 그래프의 모든 노드가 연결되어 있으면서 트리의 속성을 만족하는 그래프 신장 트리의 조건 본래의 그래프의 모든 노드를 포함해야 함 모든 노드가 서로 연결 트

2020년 6월 23일
·
0개의 댓글