욱이의 IT 생존일지

  • 홈
  • 태그
  • GitHub
  • Linkedin

최소 신장 트리 1

[BOJ/9372/Golang] 백준 9372 - 상근이의 여행

여담 MST (Minimum Spanning Tree, 최소 신장 트리) 공부 중에 MST 문제로 이 문제가 포함되어 있는 것을 보고 풀게 되었습니다. 접근 방식 처음에는 "어 그냥 노드 개수 - 1 아닌가?" 하고 "에이 설마.." 했습니다. 그러곤 MST를 공부하면서 익힌 Kruskal 알고리즘을 적용해서 풀어보고자 했습니다. 그러나 제출한 코드에 오류가 있는지 WA를 받아서 질문을 검색하다가 N-1이 답이라는 사실을 알게 되었습니다... 용어 정리 일반적인 그래프에서 사이클을 제거한 후에 Tree로 만들면, 이를 Spanning Tree라 합니다. 또한 Tree의 특성 상, 간선(edge)의 수는 정점(vertex)의 수가 N 개 일 때, N-1개가 됩니다. 이러한 상황에서 MST는 Spanning..

PS/BOJ 2021.05.25
1
더보기
프로필사진

Go언어와 Kubernetes를 좋아하는 엔지니어입니다. 꾸준히 배웁니다.

  • 전체 보기 (162)
    • PS (20)
      • BOJ (20)
    • IT (127)
      • Hadoop (1)
      • Airflow (7)
      • DevOps (6)
      • IT WIKI (25)
      • Network (16)
      • Kubernetes (18)
      • Docker (1)
      • containerd (2)
      • Istio (1)
      • Go (19)
      • OpenSource (1)
      • Python (5)
      • C++ (3)
      • OpenStack (6)
      • OS (10)
      • SQL (1)
      • Coding Tip (4)
    • 욱이야기 (7)
      • 욱이 취업 (1)
      • 욱이 (6)
    • Apple (7)
      • Mac (7)
      • iPhone & iPad & Acc (0)
    • 경제 공부 (1)
      • 부동산 공부 (1)

최근글

인기글

Tag

고랭, Coding Test, Container, 고언어, Golang, 쿠버네티스, go언어, k8s, Kubernetes, 백준, Network, Go, 컨테이너, 네트워크, 도커, BOJ, linux, 리눅스, 고, docker,

최근댓글

Archives

Calendar

«   2025/05   »
일 월 화 수 목 금 토
1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30 31

방문자수Total

  • Today :
  • Yesterday :

Copyright © Kakao Corp. All rights reserved.

  • Wookiist GitHub
  • Wookiist Linkedin

티스토리툴바