도시를 연결하는 가장 저렴한 방법? 최소 스패닝 트리 완벽 가이드 - 코드카인 티스토리

안녕하세요😊 코드카인 여러분!

오늘은 알고리즘을 공부하면서 꼭 만나게 되는 두 가지 문제를 다뤄볼게요. 바로 최소 스패닝 트리(Minimum Spanning Tree, MST)와 거스름돈 문제(Greedy Algorithm)입니다. 이 두 가지는 일상생활에서도 쉽게 비유할 수 있을 만큼 흥미로운 주제랍니다. 같이 탐구해 볼까요? 😊

---

📌 최소 스패닝 트리란?

최소 스패닝 트리를 이해하려면, 마치 도시를 연결하는 도로를 깔 때 최소 비용을 계산하는 일과 같다고 생각해보세요. 모든 도시를 연결하되, 비용이 최소가 되도록 도로를 건설하는 게 목표죠.

핵심 개념

• 그래프: 도시와 도로를 생각해요. 도시(노드)와 도로(간선)로 표현됩니다.
• 스패닝 트리: 그래프의 모든 노드를 연결하지만, 순환(사이클)은 없는 구조예요.
• 최소 비용: 스패닝 트리 중에서도 가장 비용이 적은 것을 찾는 게 핵심입니다.

주요 알고리즘

1. 크루스칼 알고리즘(Kruskal) :
   • 가장 작은 간선부터 선택해 나가는 방식.
   • 사이클이 생기지 않도록 주의하며 간선을 추가합니다.
   • 활용 예: 철도 건설 계획, 네트워크 케이블 배치.
2. 프림 알고리즘(Prim) :
   • 특정 시작점에서 출발하여 인접한 간선 중 최소 비용을 선택.
   • 한 번 선택한 노드와 연결된 간선들만 고려합니다.
   • 활용 예: 도시 내 전력망 설계.

예제 코드

# 크루스칼 알고리즘
class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = []

    def add_edge(self, u, v, w):
        self.graph.append([u, v, w])

    def find(self, parent, i):
        if parent[i] == i:
            return i
        return self.find(parent, parent[i])

    def union(self, parent, rank, x, y):
        root_x = self.find(parent, x)
        root_y = self.find(parent, y)
        if rank[root_x] < rank[root_y]:
            parent[root_x] = root_y
        elif rank[root_x] > rank[root_y]:
            parent[root_y] = root_x
        else:
            parent[root_y] = root_x
            rank[root_x] += 1

    def kruskal(self):
        result = []
        self.graph = sorted(self.graph, key=lambda item: item[2])
        parent, rank = [], []
        for node in range(self.V):
            parent.append(node)
            rank.append(0)

        for edge in self.graph:
            u, v, w = edge
            x = self.find(parent, u)
            y = self.find(parent, v)
            if x != y:
                result.append([u, v, w])
                self.union(parent, rank, x, y)

        return result

# 예제 실행
g = Graph(4)
g.add_edge(0, 1, 10)
g.add_edge(0, 2, 6)
g.add_edge(0, 3, 5)
g.add_edge(1, 3, 15)
g.add_edge(2, 3, 4)

print("Minimum Spanning Tree:", g.kruskal())

---

📌 거스름돈 문제란?

거스름돈 문제는 마치 가장 적은 개수의 동전을 사용해 손님에게 거스름돈을 주는 일과 같아요. 항상 가장 큰 동전부터 사용하면 최적의 해를 찾을 수 있을까요?

핵심 개념

• 탐욕 알고리즘(Greedy Algorithm): 현재 상태에서 가장 최선의 선택을 반복합니다.
• 최적 부분 구조: 각 단계에서의 최선 선택이 전체 문제의 최적 해를 보장합니다.

알고리즘 동작 방식

1. 동전의 종류를 내림차순으로 정렬합니다.
2. 가장 큰 동전부터 사용하여 거스름돈을 채워 나갑니다.
3. 목표 금액을 맞출 때까지 반복합니다.

한계점

• 탐욕적 접근이 항상 최적의 해를 보장하지는 않습니다. 예를 들어, 동전 단위가 [1, 3, 4]인 경우, 탐욕법으로는 6을 만들 때 [4, 1, 1]이 아니라 [3, 3]이 최적이지만 이를 찾지 못합니다.

예제 코드

def get_change(coins, amount):
    coins = sorted(coins, reverse=True)
    result = []
    for coin in coins:
        while amount >= coin:
            amount -= coin
            result.append(coin)
    if amount == 0:
        return result
    else:
        return "Solution not possible with given coin denominations."

# 예제 실행
coins = [1, 5, 10, 50, 100, 500]
amount = 1260
print("거스름돈:", get_change(coins, amount))

---

😊 마무리하며..

최소 스패닝 트리와 거스름돈 문제는 알고리즘의 두 가지 대표적인 유형으로, 실생활 문제를 해결하는 데에도 큰 도움을 줍니다. 특히 탐욕 알고리즘은 직관적이고 쉬운 방식이지만, 항상 최적의 결과를 보장하지는 않으니 조심하세요! 😊

알고리즘 공부가 어렵게 느껴질 때, 오늘 배운 문제를 떠올리며 실생활에 어떻게 적용할 수 있을지 생각해보세요. 여러분의 성장에 큰 응원이 되기를 바랄게요! 다음 시간에도 재미있는 주제로 만나요. 😊