목록프림 알고리즘 (2)

끵뀐꿩긘의 여러가지

Java - 프림 알고리즘(Prim)

◎프림 알고리즘(Kruskal) 프림 알고리즘은 노드를 중점으로 그리디하게 최소 스패닝 트리(MST)를 찾는 알고리즘이다. 영역을 단계적으로 넓혀간다고 생각하면 이해하기 편하다. ※MST의 정의와 MST를 구하는 다른 방법인 크루스칼 알고리즘에 대한 설명 https://kkwong-guin.tistory.com/61 Java - 크루스칼 알고리즘(Kruskal) ◎최소 스패닝 트리(minimum spanning tree) 스패닝 트리(spannig tree)란 신장 트리라고도 하며, 그래프 내의 모든 정점을 사이클 없이 포함하는 트리를 말한다. 하나의 그래프는 여러 개의 스패닝 트리를 kkwong-guin.tistory.com 1. 임의의 정점을 트리에 추가한다. 2. 임의의 정점에서 인접한 정점 중 최..
JAVA/자료구조-알고리즘&함수 정리 2021. 5. 26. 16:02
프로그래머스 - 섬 연결하기 (sol.java)

◎문제 링크 https://programmers.co.kr/learn/courses/30/lessons/42861 코딩테스트 연습 - 섬 연결하기 4 [[0,1,1],[0,2,2],[1,2,5],[1,3,1],[2,3,8]] 4 programmers.co.kr ◎문제 파악 모든 섬을 연결하는 최소비용 구하기 - 최소비용을 구하는 문제이므로, 그리디 알고리즘을 이용하여 섬을 잇는 비용(간선 값)이 가장 작은 섬들부터 이어가야한다. --> 간선 값을 기준으로 정렬(heap 자료구조 사용, array로 넣어서 정렬하는것보다 빠르다) - 각 섬들이 어떤 섬과 이어졌는지 파악하기 위해서 배열(connect)을 만들어 이어진 섬 중에 가장 작은 번호의 섬을 집어 넣는다. 모든 배열의 값이 0이 되면(섬의 번호 중 ..
JAVA/문제풀이 - 프로그래머스 2021. 5. 24. 23:39
Prev 1 Next