2023.04.23
2023. 4. 22. 23:59ㆍ회고록
728x90
오늘 Union-Find 심화 문제까지 풀이하였고 (정답 코드를 일부 참고함... 너무 어려움,.) Union-Find가 무엇인지 파악을 완료하였다.
그리고 이를 이용한 MST 구현 방법 중 크루스칼 알고리즘을 공부하고 구현하였다.
크루스칼 알고리즘은 그리디 알고리즘의 일부이며, 알고리즘의 수행시간을 잡아먹는 것 중 가장 긴 것은 sort 라고 하였다.
이를 이용한 기본 문제를 풀이하였고 처음에는 시간초과가 나왔지만 입출력을 표준 입출력으로 바꿔풀어 정답을 맞췄다.
내일은 이 알고리즘을 조금 더 풀어보고 익숙해졌다 싶어질때쯤 위상정렬을 공부할 예정이다.
https://www.acmicpc.net/problem/1922
1922번: 네트워크 연결
이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다.
www.acmicpc.net
추천 문제
추가 풀이할 문제
20040, 12852, 2887
728x90
'회고록' 카테고리의 다른 글
| 현재까지 완료 또는 진행중인 알고리즘 (0) | 2023.04.29 |
|---|---|
| 2023.04.17 (0) | 2023.04.27 |
| 2023.04.18 (0) | 2023.04.18 |
| 2023.04.13 (0) | 2023.04.13 |
| 2023.04.10 오랜만에 회고록 (0) | 2023.04.10 |