- 크루스칼 알고리즘
- Prim 알고리즘
https://www.acmicpc.net/problem/1922
1922번: 네트워크 연결
이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다.
www.acmicpc.net
크루스칼 알고리즘 기본 문제, Union-find 연산만 실수없이 구현해주면 된다.
https://www.acmicpc.net/problem/6497
6497번: 전력난
성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들
www.acmicpc.net
https://www.acmicpc.net/problem/1647
1647번: 도시 분할 계획
첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번
www.acmicpc.net
https://www.acmicpc.net/problem/4386
4386번: 별자리 만들기
도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일
www.acmicpc.net
https://www.acmicpc.net/problem/2887
2887번: 행성 터널
첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이
www.acmicpc.net
https://www.acmicpc.net/problem/1944
1944번: 복제 로봇
첫째 줄에 미로의 크기 N(4 ≤ N ≤ 50)과 열쇠의 개수 M(1 ≤ M ≤ 250) 이 공백을 사이에 두고 주어진다. 그리고 둘째 줄부터 N+1째 줄까지 미로의 정보가 주어진다. 미로는 1과 0, 그리고 S와 K로 주어
www.acmicpc.net
https://www.acmicpc.net/problem/9373
9373번: 복도 뚫기
각 테스트 케이스마다 센서에 감지되지 않고 복도를 지나갈 수 있는 원형 물체의 최대 반지름을 부동소수점 실수로 한 줄에 출력한다. 물체는 매우 정밀하게 움직일 수 있다고 가정한다. 만약
www.acmicpc.net
'자료구조 + 알고리즘' 카테고리의 다른 글
최대 유량 알고리즘 (0) | 2021.09.14 |
---|---|
최단거리 알고리즘 (0) | 2021.09.14 |
BFS (너비우선탐색) (0) | 2021.09.14 |
DFS (깊이우선탐색) (0) | 2021.09.14 |
정렬 알고리즘 (Sorting algorithm) (0) | 2021.09.14 |