프로그래밍 공방

트리의 중앙 정점 트리에서 다른 모든 정점까지의 거리의 합이 최소가 되는 정점 중앙 정점을 구하기 위해서는 트리의 임의의 정점에서 다른 모든 정점까지의 거리의 합을 알아야 한다. 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..

플로이드 와샬 : Floyd Warshall 가중치가 있는 그래프에서 모든 정점의 쌍에 대해 최단 경로를 찾는 알고리즘 * 플로이드 와샬 알고리즘은 다이나믹 프로그래밍의 한 예로 핵심 아이디어는 아래와 같다. 어떤 두 정점 사이의 최단 경로는 어떤 경유지를 거치거나 거치지 않는 경로 중 하나 예시 위와 같은 그래프가 있을 때, 각 정점에서 정점으로의 최단 경로를 나타내는 배열은 우측과 같다. 자기 자신은 0이고 간선이 존재하지 않는다면 INF를 넣어준다. 모든 경로에 대해 경유지 K를 거쳐갔을 때와 비교해가며 최단 경로를 계산해준다. -> A-B와 A-K + K-B를 비교한다. * 특징 - 모든 가능한 경유지에 대해 모든 정점에서 다른 모든 정점으로 가는 최단 거리를 확인하므로 O(n^3)가 걸린다. -..

위상 정렬 : Topological Sorting 위상 정렬은 선후 관계가 정의된 DAG(Directed Acyclic Graph, 유향 비순환 그래프)에서 꼭지점들을 선후 관계를 거스리지 않도록 나열하는 정렬이다. (대표적인 예로 선수과목 구조가 있다.) 위상 정렬은 그래프의 구조에 따라 아래와 같이 여러 개의 종류가 나올 수 있다. ( 1 - 7 - 3 - 4 - 5 - 2 | 1 - 4 - 7 - 5 - 2 - 3 | ... ) * 위상 정렬이 성립하기 위해서는 반드시 그래프에 순환이 존재하지 않아야 한다. 위상 정렬의 과정 1. 자기 자신을 가리키는 변이 없는 꼭짓점을 찾는다. 2. 찾은 꼭짓점을 출력하고 출력한 꼭짓점과 그 꼭짓점에서 출발하는 변을 삭제한다. 3. 아직 출력되지 않은 꼭짓점이 있..

Lower Bound : 찾는 값과 같거나 큰 값이 처음으로 나타나는 위치 (이상) Upper Bound : 찾는 값 보다 큰 값이 처음으로 나오는 위치 (초과) [1, 2, 5, 7, 8, 9, 11, 11, 11, 14] 인 배열에서 11의 Lower Bound와 Upper Bound의 과정은 아래와 같다. Lower Bound Upper Bound Lower Bound / Upper Bound 코드 12345678910111213141516171819public static int lowerBound(int[] arr, int value) { int s = 0, m, e = arr.length-1; while(s

최소 공통 조상 알고리즘은 트리 구조에서 두 정점 a, b에서 가장 가까운 공통 조상을 찾는 알고리즘이다 위 트리에서 두 정점 (4, 7)의 LCA는 1이고, (12, 11)의 LCA는 8이다. 위 트리를 예로 들었을 때, DP를 통해 a와 b의 LCA를 구하는 방법은 다음과 같다. 1. 먼저 트리를 한번 순회하며 각 정점에 대한 깊이와 부모를 정해준다. 2. 계산된 depth의 최댓값을 가지고 각 정점에 대해 2^i 번째 조상을 저장하는 배열을 만든다. 이때, 2^i 번째 조상을 찾아가는 식은 다음과 같다. parent[i][v] = parent[i-1][parent[i-1][v]] * 이 식을 말로 풀어보면 정점 v의 2^i 번째 부모는 정점 v의 2^(i-1) 번째 부모 노드의 2^(i-1) 번째 ..