코드를 읽고 설명하면, 합격합니다
이 레슨과 관련된 학습 키워드
알고리즘 — 문제 해결의 체계적 접근 → 고급 알고리즘
안녕하세요, 오늘은 {MST→엠에스티}, 최소 신장 트리에 대해 알아볼 거예요.
여러분, 5개 도시를 도로로 연결한다고 상상해 보세요.
모든 도시를 연결하되, 건설 비용을 최소화하고 싶잖아요? 바로 이게 {MST→엠에스티} 문제예요.
그림 왼쪽을 보세요. 5개 노드 A부터 E까지 총 8개 간선이 있고, 각 간선에 가중치가 적혀 있어요.
모든 간선을 다 쓰면 비용이 너무 크겠죠?
그래서 딱 필요한 간선만 골라서 모든 노드를 연결하는 거예요.
오른쪽 초록색 그래프를 보세요. 간선 4개만으로 5개 노드를 전부 연결했어요.
선택된 간선은 E-C 가중치 1, B-C 가중치 2, C-D 가중치 3, A-B 가중치 4예요.
총 비용은 10이고, 이보다 적은 비용으로 모든 노드를 연결하는 건 불가능해요.
여기서 핵심은, 이 결과가 트리라는 거예요. 트리는 사이클이 없는 연결 그래프예요.
하단 왼쪽 파란 박스를 보세요. 첫 번째 성질: 정점 V개면 간선은 정확히 V-1개예요.
가운데 빨간 박스를 보면, 두 번째 성질: 사이클이 없어요.
간선 하나를 제거하면 그래프가 두 조각으로 분리돼요. 그만큼 간결한 구조예요.
오른쪽 초록 박스는 세 번째 성질: 모든 가능한 신장 트리 중에서 가중치 합이 가장 작아요.
왜 하필 트리여야 할까요? 사이클이 있으면 불필요한 간선이 포함된 거니까요.
사이클 속 가장 무거운 간선을 빼도 연결성이 유지되거든요.
그래서 {MST→엠에스티}는 항상 트리 형태가 되는 거예요.
{MST→엠에스티}를 구하는 대표적 알고리즘으로 {Kruskal→크루스칼}과 {Prim→프림}이 있는데, 곧 하나씩 배울 거예요.
네트워크 설계, 클러스터링, 도로망 최적화 등 실전에서도 정말 많이 쓰여요.
자, 이제 {MST→엠에스티}가 뭔지 감이 잡히셨죠? 다음 슬라이드에서 핵심 도구인 {Union-Find→유니온파인드}를 배울 거예요.