두달만에 다시 글을 쓰네요!
대학에 입학하고 나니 개인적인 공부를 할 시간이 많아져 확실히 좋은 것 같습니다 ㅎㅎ
고등학교 시절엔 "지금 공부 안 하면 큰일난다!!"는 마인드로 공부했었던 것 같은데, 지금은... 뭐 하면 좋고 안 해도 그만이고 ㅋㅋㅋㅋㅋㅋ
고등학교 친구들 공부하는거 보면 그동안 어떻게 버텨왔던건지 참 신기하네요
아무튼간에, 교내 알고리즘 동아리에서 매주 세미나를 진행하는데, 연습문제를 모두 풀면 동아리비를 환급해준다는 말을 듣고(!!) 이번 주차 연습문제를 한번 풀어보았습니다.
최소/최대 스패닝 트리가 아닌 아무 스패닝 트리만 구해 출력하는 문제이다. 주어진 그래프에 사이클이 존재한다면 ($V\leq E$) 서로 다른 스패닝 트리가 적어도 3개 존재한다는 것을 알 수 있다. 따라서, 크루스칼 알고리즘을 따라 진행하다가, union-find를 통해 최초로 사이클이 생기는 간선을 찾으면, 해당 간선을 이어주고 다시 처음부터 크루스칼을 돌려 찾고자 하는 스패닝 트리를 얻을 수 있다.
유니온 파인드를 활용한 쿼리 문제이다. 먼저 술을 자기가 전부 마실 수 있다면 마신다. 그렇지 않을 경우, Union 연산을 통해 자신의 부모 노드를 다음 사람의 부모 노드로 설정한다. 그리고 남은 술을 자신의 부모 노드가 가리키는 사람에게 넘겨준다. 여기서 자신의 부모 노드가 뜻하는 것은 다음으로 술을 마실 수 있는 (만취하지 않은) 사람이다. 이러한 과정을 술을 모두 마실 때 까지 반복하면, 시간복잡도 $O(N+Q)$에 문제를 해결할 수 있다. set과 set의 upper_bound 메서드를 이용해 해결하는 방법도 있는 것 같다.
17352: 여러분의 다리가 되어 드리겠습니다! (G5, Union-Find)
우선 유니온 파인드를 이용해 섬을 두 그룹으로 분류한다. 그리고, 1번 섬과 다른 그룹에 있는 아무 섬이나 하나 찾아 두 섬을 연결해주면 된다.
최소 스패닝 트리를 찾는 문제와 유사하지만, 간선을 잇는 대신 새로운 정점을 추가할 수 있다! 프림 알고리즘을 응용해서, 매 for문마다 이을 수 있는 가장 저렴한 간선의 비용과 우물을 새로 짓는 데 필요한 가장 작은 비용을 비교한다. N이 작기 때문에 단순 배열로 구현하여 시간복잡도 $O(N^2)$로 문제를 해결할 수 있다. 가상의 정점을 두어 일반적인 MST 알고리즘으로 푸는 방법도 있는 것 같다.
'PS > 공부' 카테고리의 다른 글
| 2024-01-21 PS 공부 (1) | 2024.01.21 |
|---|---|
| 2023-12-13 PS 공부 (0) | 2023.12.13 |
| 2023-12-06 PS 공부 (0) | 2023.12.06 |
| 2023-12-03 PS 공부 (0) | 2023.12.04 |