다섯 살도 알 수 있게 · 시스템SW
최소신장트리(MST)가 뭐예요?
최소신장트리를, 정비공장 여러 지점을 배관 비용 합이 가장 적도록 사이클 없이 모두 연결하는 이야기로 풀어봤어요.
지점 다섯 곳을 전부 배관으로 이어야 해요.배관 길도 많고 비용도 제각각이라 고민이에요.
배관을 전부 다 놓으면 연결은 되지만 돈이 너무 많이 들어요.꼭 필요한 배관만 골라 돈을 아끼고 싶어요.
최소신장트리는 배관 비용의 합이 가장 적도록, 사이클 없이 모든 지점을 잇는 것이에요.초록 배관 네 개만으로 다섯 지점이 다 이어져요.
가장 싼 것부터비용이 적은 배관을 먼저 봐요
사이클 금지이미 이어진 곳은 다시 안 이어요
연결망 넓히기이어진 범위를 조금씩 키워요
다섯 지점 모두 연결다섯 지점이 하나도 빠짐없이 이어져요
배관을 고르는 대표 방법은 크루스칼과 프림, 두 가지예요.크루스칼은 배관 전체를 보고 고르고, 프림은 한 지점에서 연결망을 넓혀가요.
가장 싼 길만 고집하면 사이클이 생길 수 있어요.'가장 싸게'와 '사이클 없이' 둘 다 지켜야 진짜 MST예요.
한 줄로
최소신장트리(MST)는 여러 지점을 길 비용의 합이 가장 적도록, 사이클 없이 전부 연결하는 방법이에요.
최소신장트리는 가중치가 있는 그래프에서 모든 정점을 사이클 없이 연결하면서 간선 가중치의 합이 최소가 되는 부분 그래프예요. 크루스칼 알고리즘은 모든 간선을 가중치 순으로 정렬한 뒤, 사이클을 만들지 않는 한 가장 싼 간선부터 차례로 선택해요(유니온-파인드로 사이클을 검사). 프림 알고리즘은 한 정점에서 시작해 이미 연결된 집합과 바깥을 잇는 가장 싼 간선을 반복해서 추가하며 트리를 키워가요. 둘 다 정점이 n개면 간선이 n-1개인 트리가 만들어져요.
어른들은 이렇게 불러요
- 최소신장트리(MST)
Minimum Spanning Tree - 배관 비용 합이 가장 적게 모두 잇는 연결망. 정점이 n개면 간선은 n-1개예요.
- 크루스칼 알고리즘
Kruskal's Algorithm - 싼 배관부터 차례로 고르는 방법. 전체 배관을 미리 정렬해두고 골라요.
- 프림 알고리즘
Prim's Algorithm - 한 지점에서 시작해 넓혀가는 방법. 이미 이은 곳에서 가장 싼 길만 넓혀가요.
- 사이클(순환)
Cycle - 배관이 빙 둘러 다시 이어지는 것. MST에서는 생기면 안 돼요.
- 가중치 그래프
Weighted Graph - 배관마다 비용이 적힌 지도. MST는 이 비용의 합을 최소화해요.
- 유니온-파인드
Union-Find - 이미 이어졌는지 빠르게 확인하는 도구. 크루스칼에서 사이클 검사에 써요.
- 탐욕 알고리즘
Greedy Algorithm - 매번 당장 가장 싼 것을 고르는 전략. 크루스칼·프림 둘 다 이 전략이에요.
- 최단경로 알고리즘
Shortest Path Algorithm - 두 지점 사이 가장 싼 '한 길'을 찾는 것. MST는 '모두 잇기'가 목표라 다른 문제예요.
다음 이야기
덮어쓰지 않는 부품 창고 관리인 →