문제 https://www.acmicpc.net/problem/11438 11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 설명 트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다. 두 노드의 쌍 M개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력해야 한다. 각 정점의 방문 여부를 체크하기 위한 check 배열과 각 정점의 깊이를 저장할 depth 배열을 만든다. 그리고 각 정점의 \(2^k\) 번째 부모를 저장하기 위해 parent[18][] 배열을 만든다...
최소 공통 조상 (Lowest Common Ancestor / LCA) 정점 A와 정점 B가 각각 자신을 포함하여 조상을 따라 거슬러 올라갈 때 처음 공통으로 만나게 되는 정점 정점 A 혹은 A의 조상이면서 정점 B 혹은 B의 조상인 정점들 중 가장 깊은 정점 위의 그림에서 13번 정점과 15번 정점의 최소 공통 조상은 5번 정점이 된다. 최소 공통 조상 구하기 선형 탐색 : \(O(depth) = O(N)\) 1. 최상위 조상 정점을 시작으로 DFS 또는 BFS를 수행하여 각 정점의 깊이와 부모 정점을 저장한다. 2. 최소 공통 조상을 찾을 두 정점을 확인한다. 3. 먼저 두 정점의 깊이가 같아질 때까지 각각 부모를 따라 거슬러 올라간다. 4. 이때, 가리키는 정점이 다르다면 다시 각각 부모를 따라 하..
문제https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다.www.acmicpc.net 설명각 컴퓨터를 연결하는데 필요한 비용이 주어졌을 때 모든 컴퓨터를 연결하는데 필요한 최소비용을 구해야 한다.이번 문제에서는 크루스칼 알고리즘을 통해 최소 신장 트리를 구할 것이다.먼저 간선의 정보를 저장할 Edge 클래스를 만든다.우선순위 큐에서 가중치를 기준으로 오름차순으로 정렬하기 위해 Comparable 인터페이스를 이용한다.static class Edge implements Comparable { int current; int dest; int cost; ..
문제 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 설명 최소 스패닝 트리는 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다. 이번 문제에서는 프림 알고리즘을 통해 최소 신장 트리를 구할 것이다. 먼저 간선의 정보를 저장할 Edge 클래스를 만든다. 우선순위 큐에서 가중치를 기준으로 오름차순으로 정렬하기 위해 Comparable 인터페이스를 이용한다. c..
트리 무향 그래프이면서, 순환이 없는 연결 그래프 트리의 어떤 두 정점에 대해서 단순 경로가 하나 존재한다. 신장 트리 무향 연결 그래프의 부분 그래프이고, 해당 그래프의 모든 정점을 포함하는 트리 다음은 무향 연결 그래프에 대한 4가지 신장 트리이다. (E = V - 1) 깊이 우선 신장 트리와 너비 우선 신장 트리 깊이 우선 신장 트리는 무향 연결 그래프에서 DFS으로 탐색하면서 생성된 신장 트리이다. 너비 우선 신장 트리는 무향 연결 그래프에서 BFS으로 탐색하면서 생성된 신장 트리이다. 최소 신장 트리 (Minimum Spanning Tree / MST) 무향 연결 가중 그래프에서 간선의 가중치의 합이 최소인 신장 트리 그래프에서 최소 신장 트리를 만드는 알고리즘으로는, 크루스칼 알고리즘과 프림 ..
문제 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 설명 (n + 1) 개의 집합 { 0 }, { 1 }, { 2 }, ... , { n } 이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 각 (n + 1) 개의 집합은 서로소 집합이다. 합집합 연산이 필요할 때에는 union()를 사용하고 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산이..
서로소 집합 교집합이 공집합인 집합(서로소 집합)들의 정보를 확인(Find)하고 조작(Union)할 수 있는 자료구조 - Union 연산 어떤 두 원소 a, b 에 대해서, union(a, b)는 각 원소가 속한 집합을 하나로 합치는 연산이다. \(a \in A, b \in B\) 에 대해서, union(a, b)는 \(A \cup B\) 이다. - Find 연산 어떤 원소 a에 대해서, find(a)는 a가 속한 집합(집합의 대표번호)을 반환하는 연산이다. \(a \in A\) 에 대해서, find(a)는 집합 A(집합 A의 대표번호)를 반환한다. 서로소 집합의 표현 - 초기화 - Union 연산 ex) union(1, 2) - Find 연산 ex) find(3) = 1, find(5) = 1 서로소 ..
문제 https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 설명 어떤 건물을 짓기 위해서 다른 건물을 먼저 지어야 할 수도 있다. 여러 개의 건물을 동시에 지을 수 있다. 건물을 짓는데 우선순위가 있으므로 이는 DAG로 나타낼 수 있다. 먼저 건물을 짓는데 걸리는 시간과 후행자로 가지는 건물 번호 리스트를 저장할 Build 클래스를 만든다. class Build { int time; ArrayList successor; public Bui..
