본문 바로가기

Algorithm98

boj 1197 - 최소 스패닝 트리(MST, kruskal) 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 MST를 구할 때 사용하는 알고리즘은 프림, 크루스칼 알고리즘이 있다. (V, E)가 각각 그래프의 노드, 엣지의 갯수 일때 노드를 기준으로 MST를 찾아나가는 프림 알고리즘은 은 복잡도가 O(V*E) = O(V^3)이고, 엣지를 기준으로 Disjoint set을 합치면서 사이클이 생기지 않았는지 검사하는 union-find 알고리즘을 이용하면 복잡도가 O(Elog.. 2021. 3. 28.
1922- 네트워크 연결 C++(MST, prim or kruskal, BFS) www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 최소 스패닝 트리를 만드는 문제이다. MST를 구하는 알고리즘에는 프림, 크루스칼 알고리즘이 있는데, 그 중 정점을 기준으로 최소비용 엣지을 추가해나가며 MST를 만들어나가는 프림 알고리즘을 이용했다. 크루스칼 알고리즘은 간선을 기준으로 사이클이 만들어지는 지 여부를 union-find 알고리즘으로 파악해나가면서 최소비용 엣지을 MST에 추가해 나가는 알고리즘이다. priority_queue을 이용해서 특정 노드에서 갈 수 있는 엣지의 최소값을 찾아내고, bfs를 하면서 방문해나간다. 우선순위 큐를 .. 2021. 3. 28.
[boj] 2056 - 작업 C++ 풀이(DAG, BFS) www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 작업의 선행관계가 주어졌을 때, 모두 마치는 가장 빠른 시간을 구하는 문제이다. 전형적인 DAG문제이고, 위상정렬 로직을 bfs로 구현해서 모든 노드를 순서대로 순회했을 때의 최종 시간을 구하면 된다. #include #include #include #include using namespace std; int n; vector graph[10001]; vector ind(10001); // indegr.. 2021. 3. 28.
[boj] 2252 - 줄 세우기 C++(DAG, topological sort) www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이 www.acmicpc.net 간단하게 위상정렬에 대해서 배울 수 있는 문제이다. 사이클이 없는 유향그래프인 DAG를 통해서 선행관계를 구현할 수 있는 알고리즘이 위상정렬이다. 위상정렬은 출력 방법에 따라서 여러 개의 답이 나올 수 있고, DFS, BFS 방식으로 구현할 수 있는데 BFS가 좀 더 간단해보인다. 밑의 방식은 BFS방식이며, indegree가 0인 노드를 큐에 넣으면서 노드를 소거하는 식으로 다.. 2021. 3. 26.

티스토리툴바