4luv1015

https://www.acmicpc.net/problem/30831 30831번: 선후수과목 첫 번째 줄에 과목 이수 체계도에 포함된 과목의 수 $N$, 권장 선후수 관계의 수 $A$, 필수 선후수 관계의 수 $B$가 공백으로 구분되어 주어진다. $(1 \leq N \leq 1\ 000\ 000; \ 0 \leq A, B; \ A+B \leq N-1)$ 다음 www.acmicpc.net 2023 uospc(서울시립대 컴퓨터과학부 알고리즘 경진대회) div2의 최고 난이도 문제이다. 직접 참가했던 대회이니만큼 대회에 관해 얘기를 조금 하자면, 큰 대회가 아닌지라 당시 꽤나 자신만만히 대회에 참가했었는데 아쉽게 2등으로 대회를 마무리했다. 못 풀었던 문제 전부가 알고보니 상당히 스탠다드하거나 웰노운한 문제,..

https://www.acmicpc.net/problem/1833 1833번: 고속철도 설계하기 첫째 줄에 자연수 N이 주어진다. 다음 N개의 줄에는 인접행렬 형태로 두 도시 사이에 고속철도를 설치할 때 드는 비용이 주어진다. 이 비용은 각각 10,000을 넘지 않는 자연수이다. 만약 비용이 음 www.acmicpc.net 문제를 읽어보면 최소 스패닝 트리 알고리즘으로 문제를 풀 수 있다는 것을 쉽게 떠올릴 수 있다. 다만 기존에 연결되어 있는 간선들이 존재하기 때문에 최소 스패닝 트리 알고리즘을 적용하기 전에 우선 이미 존재하는 간선들을 통해 노드를 union한 뒤 disjoin set의 개수(즉, find를 했을 때 자기 자신이 부모인 노드의 개수)를 확인하고 그 수의 보다 하나 적은 개수만큼의 간선..