[ 2021.06.20 ] 하루 세 문제(2일차)

정유택·2021년 6월 23일
0

everyday_algorithm

목록 보기
3/8

매일 3개의 주제를 골라 문제를 풀어봅시다.

  • 슬라이딩 윈도우
  • 최소 스패닝 트리
  • 위상 정렬

슬라이딩 윈도우

최소 스패닝 트리

  • 문제 : 최소 스패닝 트리
  • 난이도 : Gold 4
  • 해설
    • 최소 스패닝 트리(MST)는 크루스칼 알고리즘과 관련이 있다.
    • 그래프의 모든 엣지를 가중치가 낮은 순서대로 연결을 하는데 이때 union-find 알고리즘을 이용하여 하나의 사이클이 생기는 것을 방지합니다. 사이클이 생기는 것을 방지하는 이유는 3개의 정점을 연결하는데 있어서 3개의 간선이 필요해지는 순간 가장 적은 비용으로 모든 정점을 연결시키는 것이 아니기 때문입니다.
    • 소스코드 : https://www.acmicpc.net/source/30220871

위상 정렬

0개의 댓글