프로그래민👨‍💻

모든 정점을 N-1개로 연결하는 MST 문제이다. MST를 해결하기 위해선 간선기준인 Kruskal 알고리즘과 정점기준인 Prim 알고리즘을 사용할 수 있다. 두 문제는 어쨋든 출발점, 도착점 비용을 알아야하기 때문에 문제에서 비용을 구하는 방법을 생각해보았다. N이 최대 100,000임으로 2중for문은 사용불가하여 고민해본 결과, 전체 정점을 x,y,z로 각 각 정렬했을때 하나 뒤의 정점과의 x,y,z 차이를 이용하여 간선을 구하는 방법을 고안하였다. 이렇게 모든 간선들의 비용을 PriorityQueue에 저장한다음 UnionFind를 이용하여 MST를 구하였다. 그래프의 간선들을 만듬에 있어 충분한 고민이 필요했던 문제였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17..

이 문제는 여지껏 배운 다양한 알고리즘을 거의다 사용해야 풀 수 있다. 다음과 같은 로직으로 구현하였다. 1. BFS 또는 DFS 를 이용하여 섬을 찾고, 1부터 차례대로 섬에 대해 인덱싱을 해주기 2. 섬의수C2 인 조합을 이용하여 두개의 섬을 고르고, 가장 자리에 대해서 DFS를 이용하여 직선경로 찾기 3. 찾은 직선 경로에 대해 그래프의 형태를 만들기 4. 만든 그래프에 대해 모든 정점을 포함하며 정점보다 하나 적은 간선을 선택하게 되는 MST를 만들기 4-1. UnionFind를 이용한 간선 기준 Kruskal알고리즘 사용 4-2. PriorityQueue를 이용한 정점 기준 Prim 알고리즘 사용 다양한 알고리즘을 한번에 적용 시켜야 했던 문제이고, 여러가지를 다시 복습할 수 있어던 기회여서 좋..

최소신장트리를 찾는 MST문제이다. 이문제를 해결함에 있어 간선중심의 Kruskal 알고리즘 대신, PriorityQueue를 활용한 Prim 알고리즘을 사용하였다. Edge라는 클래스를 만들어서 weight를 기준으로 빠른 값이 올수있게 최소힙을 사용하는 PriorityQueue를 사용하였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 8..

MST 문제이다. 이 문제를 풀기 위해선 Kruskal 이나 Prim을 사용해야한다. 참고 이 문제를 두가지방법 모두 사용하여 풀어보았다. 첫번째로 Kruskal 알고리즘을 사용하였는데 , 정렬을 함에 있어 PriorityQueue를 사용하였고, 같은 팀임을 보기 위해 UnionFind를 같이 사용하였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 7..

최소신장트리 즉, MST를 구하는 문제이다. 최소신장트리란 , 그래프에서 V개의 접점과 E개의 간선이 있을 때, V-1개의 간선으로 이루어진 트리로 싸이클이 생겨나지 않고, 방향이 없으며 간선들의 합이 최소일 때를 말한다. 구하는 대표적인 알고리즘으로는 Kruskal, Prim이 있다. ※그래프 정점V 와 간선E로 이루어진 연결관계를 모아 놓은 자료. 프로그래밍상 표현법은 다음과 같다. - 간선의 배열 : 정점과 정점의 연결정보인 간선을 모아놓음 - 인접 리스트 : 각 정점별로 연결된 정점의 정보를 모아놓음(ex. List[]) - 인접행렬 : 2차원 행렬에 각 정점과 정점간의 연결정보를 표시(ex. arr[][]) ※Kruskal 알고리즘 그래프에서 간선을 기준으로 MST를 찾고 싶을 때 사용하는 알고..