어차피 둘다 목적은 확실하니까 하나만 알면 되나
- dc official App
[일반] mst 크루스칼 프림 둘다 알아야함?
익명(220.122)
2020-03-09 04:05
추천 0
댓글 7
다른 게시글
-
오늘의 ps [6][일반] 익명(39.7) | 20.03.09추천 2
-
solved.ac는 언제쯤 통합될거임? [1][일반] 익명(14.49) | 20.03.09추천 0
-
돌이켜보니 5달동안 800점을 올렸음 [4][일반] 익명(211.202) | 20.03.09추천 0
-
새로운 알고리즘 배우는거 넘 재밋다 [1][일반] 익명(211.227) | 20.03.08추천 0
-
코포에서 뚝배기 깨졌는데요 [1][일반] NewB(braveinno) | 20.03.08추천 0
-
코포 원래 렉 좆댐? [1][일반] 익명(218.52) | 20.03.08추천 0
-
종만북 그래프파트 고대어사전 문제 질문점.... [1][일반] 익명(119.70) | 20.03.08추천 0
-
Codeforce에 dcinside라는 닉네임 가지신분 [11][일반] 앞머리내렸..(dtc03012) | 20.03.08추천 1
-
코딩시간 줄이는법좀 [3][일반] 익명(39.7) | 20.03.08추천 0
-
재채점 웨이브다[일반] 최상급경화..(112.187) | 20.03.08추천 0
둘 시간복잡도가 다른걸로 아는데 크루스칼이 확장성이 좋다고 합니더
예를들어 어떤 두 정점 a-b사이 경로 중 간선가중치의 최댓값이 최소인 경로 구하기
크루스칼처럼 가장 작은 가중치 간선부터 추가하다가 a와 b가 연결되는순간 그게 정답
PBS!
크루수칼 배우면 유니온파인드도 공부해야되서 더좋음
보통은 크루스칼이면 되고 프림을 쓰는건 별로 본적이 없음. 근데 보루브카라고 하나 또있는데 그건 방식이 차이가 커서 가끔 응용하는 문제가 나옴
그 최대 가중치를 가진 트리 지름 구할라면 프림 알아야댐