가성비 최고의 네트워크 구축하기 (1)
크리스에게 새로운 임무가 떨어졌다.
"회사 사무실이 5군데(A, B, C, D, E) 있는데, 이들을 모두 연결하는 내부 네트워크망을 구축해 주세요. 단, 케이블 비용이 비싸니까 가장 적은 비용으로 모든 사무실을 연결해야 합니다."
크리스는 고민에 빠졌다.
"A랑 B를 잇는 건 10만 원, A랑 C는 5만 원... 전부 다 연결하면 돈이 너무 많이 드는데? 사이클(순환) 없이 딱 필요한 만큼만 연결해서 비용을 최소화할 수는 없을까?"
이것이 바로 컴퓨터 과학에서 말하는 최소 신장 트리(Minimum Spanning Tree, MST) 문제다. 도시 가스 파이프 설치, 전력망 구축 등 **"최소 비용으로 모든 지점을 연결"**해야 하는 모든 곳에 쓰이는 알고리즘이다.
1. 신장 트리(Spanning Tree)란?
쉽게 말해 **"가성비 있게 모든 점을 잇는 방법"**이다. 이를 구하는 대표적인 알고리즘 두 가지, **크루스칼(Kruskal)**과 **프림(Prim)**을 알아보자.
2. 크루스칼 알고리즘 (Kruskal's Algorithm)
크루스칼은 아주 직관적이고 "욕심쟁이(Greedy)" 같은 방식이다.
"가장 싼 케이블부터 일단 쓰고 보자!"
사이클은 어떻게 알지? (Union-Find)
크루스칼 알고리즘의 핵심은 "이 선을 그으면 사이클이 생기나?"를 판단하는 것이다.
이를 위해 **Union-Find(유니온 파인드)**라는 자료구조를 사용한다. "A와 B가 이미 같은 집합(연결됨)인가?"를 $O(1)$에 가깝게 확인해 준다.
JavaScript
// 간단한 크루스칼 로직 (개념) function kruskal(n, edges) { // 1. 비용순 정렬 edges.sort((a, b) => a.cost - b.cost); const parent = Array.from({ length: n }, (_, i) => i); // Union-Find용 배열 let totalCost = 0; // 부모 찾기 (Find) const getParent = (x) => { if (parent[x] === x) return x; return parent[x] = getParent(parent[x]); }; // 합치기 (Union) const unionParent = (a, b) => { const rootA = getParent(a); const rootB = getParent(b); if (rootA < rootB) parent[rootB] = rootA; else parent[rootA] = rootB; }; // 2. 간선 선택 for (const { from, to, cost } of edges) { // 부모가 다르면(연결 안 되어 있으면) 연결! if (getParent(from) !== getParent(to)) { unionParent(from, to); totalCost += cost; } } return totalCost; }
3. 프림 알고리즘 (Prim's Algorithm)
프림 알고리즘은 "땅따먹기" 방식이다.
크루스칼이 "전국 각지에서 싼 것부터 연결"한다면, 프림은 "시작점에서부터 조금씩 뻗어나가는" 방식이다.
4. 크루스칼 vs 프림: 승자는?
하지만 대부분의 코딩 테스트나 실무 문제에서는 구현이 더 직관적인 크루스칼 알고리즘을 많이 사용한다.
5. 3장을 마치며
우리는 3장에서 데이터를 찾는 다양한 방법을 배웠다.
이제 우리는 효율적인 경로를 찾고, 데이터를 정렬하는 법을 안다.
하지만 알고리즘의 세계에는 "답을 구하긴 구하는데, 똑같은 계산을 수백만 번 반복하느라 느려지는" 멍청한 상황들이 있다.
"한 번 계산한 건 기억해두면 안 돼?"
메모장 하나로 알고리즘 성능을 극한으로 끌어올리는 기술. 4장의 주제는 바로 **동적 프로그래밍(Dynamic Programming)**이다.
4장 동적 알고리즘 - 1. 동적 프로그래밍이란? 편에서 계속된다.