프로그래밍 공방

트리의 중앙 정점 트리에서 다른 모든 정점까지의 거리의 합이 최소가 되는 정점 중앙 정점을 구하기 위해서는 트리의 임의의 정점에서 다른 모든 정점까지의 거리의 합을 알아야 한다. i에서 i의 서브트리에 속하는 모든 정점들까지의 거리의 합을 vSum[i], i에서 i의 서브트리에 속하지 않는 모든 정점들까지의 거리의 합을 rSum[i] 이라 할 때, 정점 i에서 다른 모든 정점까지의 거리의 합은 vSum[i] + rSum[i]로 나타낼 수 있다. 1. i에서 i의 서브트리에 속하는 모든 정점들까지의 거리의 합 (vSum[i]) vSum[i]을 구하기 위해서는 i의 직계 자손들을 서브트리의 루트로 하는 정점들의 vSum[i의 직계자손]와 그 서브트리에 속하는 총 정점의 수(vCount[i의 직계자손])가 필..

크루스칼 알고리즘 : Kruskal's Algorithm 최소 비용 신장 부분 트리(MST)를 찾는 알고리즘 Spanning Tree : 신장 트리 트리의 특수한 형태로 모든 정점들이 연결되어 있고 사이클을 포함하지 않는 트리 ( * 한 노드에서 다른 노드에 이르는 경로가 오직 하나 뿐인 트리 ) MST(Minimum Spanning Tree) : 최소 신장 트리 Spanning Tree 내 모든 간선의 가중치의 합이 최소인 트리 시간 복잡도 O(ElogV) * 변의 개수 : E, 꼭짓점의 개수 : V 과정 1. 정점별로 parent를 자기 자신으로 초기화 해준다. 2. 입력으로 주어진 간선들을 가중치를 기준으로 오름차순 정렬해준다. 3. 간선을 순서대로 순회하면서 양 끝 정점의 parent를 확인하고(..

다익스트라 알고리즘 : Dijkstra Algorithm 그래프에서 특정 꼭짓점에서 다른 모든 꼭짓점 간의 최단 경로를 찾는 알고리즘 시간 복잡도 1. 우선순위 큐를 사용하지 않는 경우 : O(V^2) 2. 우선순위 큐를 사용하는 경우 : O(ElogV) 코드 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106import java.util.ArrayList;import java.uti..