https://www.acmicpc.net/problem/11438알고리즘 분류 : 자료 구조, 트리, 최소 공통 조상, 희소 배열❓문제🔅해석순서input된 값을 adjacent list(양방향 간선)에 넣는다.BFS로 트리 탐색bfs로 트리를 탐색하면서 각 노드의 깊이(depth)와 부모(parent)를 기록한다. 희소 테이블(Sparse Table) 구성각 노드에 대해 2^k번째 부모를 미리 계산한다. 이 테이블을 이용하면, 두 노드의 깊이를 맞춘 후, 공통 조상을 빠르게 찾을 수 있다.Find LCA항상 b가 a보다 depth가 큰 노드(root로부터 먼)가 되도록 swapa, b의 depth 맞추기(0.에 의해 항상 b를 끌어올리게 된다)2에서 depth를 맞추었는데 a와 b가 같다면 lca를 ..
https://www.acmicpc.net/problem/1922알고리즘 분류 : 그래프 이론, 최소 스패닝 트리❓문제🔅해석컴퓨터 == 정점선 == 간선 모든 컴퓨터(정점)를 연결하여 최소의 비용(가중치)을 얻기 위해 MST를 구현한다.MST를 구하기 위한 알고리즘에는 크루스칼, 프림이 있는데 크루스칼로 풀이해본다. // input691 2 51 3 42 3 22 4 73 4 63 5 114 5 34 6 85 6 8 1. 간선 정렬그래프의 모든 간선을 가중치 기준으로 오름차순 정렬한다. 2. 간선 선택정렬된 간선 리스트에서 순차적으로 간선을 선택한다. 이때, 선택된 간선이 사이클을 형성하지 않는다면 해당 간선을 최소 신장 트리에 추가한다. 3. 사이클 검증사이클이 형성되는지 확인하기 위해서 유니온-..
그래프 (Graph)현실세계의 사물이나 개념 간의 연결 관계를 수학적 모델로 단순화하여 표현한 것 그래프 표현1. 간선 리스트(Edge List)정점의 개수가 V개, 간선의 개수가 E개인 그래프에 대해서 E x 2 (or E x 3) 이차원 배열(A)에 간선 정보를 저장어떤 두 정점 vi, vj를 연결하는 간선 ek = (vi, vj) 에 대해서 A[k][0] = vi, A[k][1] = vi가중치 그래프의 경우 배열의 3번째 열에 간선의 가중치를 저장벨만-포드 알고리즘에서 사용한다.코드 구현간선 정보 classstatic class Edge{ int from; int to; int cost; public Edge(int from, int to, int cost){ th..
