[카테고리:] 파이썬 코딩테스트 강좌

안녕하세요! 오늘은 그래프 이론에서 중요한 개념 중 하나인 최소 신장 트리(MST)를 구하는 방법에 대해 알아보겠습니다. 최소 신장 트리는 연결된 모든 정점을 포함하면서도 간선의 총 가중치가 최소인 트리를 말합니다. 이 개념은 네트워크 설계, 도로 연결, 클러스터링 등 다양한 분야에서 활용됩니다.

문제 설명

문제는 다음과 같습니다:

주어진 무방향 가중 그래프에서 최소 신장 트리를 구하는 프로그램을 작성하시오. 그래프는 1 ≤ V ≤ 1000 (정점의 수) 와 1 ≤ E ≤ 10000 (간선의 수) 내에서 주어지고, 모든 간선의 가중치는 1 ≤ w ≤ 1000 입니다.

문제 풀이 접근법

최소 신장 트리를 구하는 알고리즘은 여러 가지가 있지만, 그 중 가장 많이 사용되는 두 가지 알고리즘은 프림(Prim) 알고리즘과 크루스컬(Kruskal) 알고리즘입니다. 여기에서는 프림 알고리즘을 사용하여 문제를 해결하는 방법을 설명하겠습니다.

프림 알고리즘 개요

프림 알고리즘은 항상 최소 가중치를 가진 간선을 선택하면서 진행하는 알고리즘으로, 다음과 같은 절차를 따릅니다:

1. 시작 정점을 선택합니다. (임의의 정점으로 시작 가능합니다.)
2. 현재 선택된 정점과 연결된 간선 중에서 가중치가 가장 작은 간선을 선택합니다.
3. 선택된 간선이 연결하는 정점을 트리에 추가합니다.
4. 2번과 3번의 과정을 반복하여 모든 정점을 포함할 때까지 진행합니다.

프림 알고리즘의 시간 복잡도

프림 알고리즘의 시간 복잡도는 사용되는 자료구조에 따라 달라집니다. 힙(priority queue)을 사용하면 O(E log V)의 복잡도를 가지며, 인접 행렬을 사용하면 O(V2)의 복잡도를 가집니다. 일반적으로 힙을 사용하는 것이 더 효율적입니다.

구현하기

이제 실제로 프림 알고리즘을 구현해 보겠습니다. 아래는 파이썬 코드입니다:

import heapq  # 힙을 사용하기 위해 임포트

def prim(graph, start):
    mst = []  # 최소 신장 트리 리스트
    visited = set()  # 방문한 정점 집합
    min_heap = [(0, start)]  # 힙 초기화 (가중치, 정점)

    total_weight = 0  # 총 가중치

    while min_heap:
        weight, vertex = heapq.heappop(min_heap)  # 최소 가중치 간선 선택
        if vertex not in visited:
            visited.add(vertex)  # 방문 처리
            total_weight += weight  # 가중치 합산
            mst.append((weight, vertex))

            for next_vertex, next_weight in graph[vertex].items():
                if next_vertex not in visited:
                    heapq.heappush(min_heap, (next_weight, next_vertex))  # 힙에 추가

    return mst, total_weight  # 최소 신장 트리와 총 가중치 반환

# 그래프 정의 (인접 리스트)
graph = {
    1: {2: 3, 3: 1},
    2: {1: 3, 3: 1, 4: 6},
    3: {1: 1, 2: 1, 4: 5},
    4: {2: 6, 3: 5}
}

mst, total_weight = prim(graph, 1)
print("최소 신장 트리:", mst)
print("총 가중치:", total_weight)
    

코드 설명

위 코드는 prim라는 함수를 정의하고 있습니다. 이 함수는 그래프와 시작 정점을 인자로 받아 최소 신장 트리와 그 총 가중치를 반환합니다.

• min_heap: 현재 선택 가능한 간선들을 힙으로 관리합니다.
• visited: 이미 선택된 정점을 추적하여 중복 선택을 방지합니다.
• 힙에서 최소 가중치 간선을 선택한 후, 해당 정점을 트리에 추가하고 연결된 정점들을 힙에 추가합니다.

테스트 케이스 실행

위 코드를 실행하면 다음과 같은 결과를 얻게 됩니다:

최소 신장 트리: [(0, 1), (1, 3), (1, 2)]
총 가중치: 2
    

여기서 최소 신장 트리는 정점 1, 2, 3이 포함되며, 총 가중치는 2입니다.

복잡한 예제

보다 복잡한 그래프에 대해서도 동일한 방법으로 최소 신장 트리를 구할 수 있습니다. 예를 들어, 하나의 그래프에 여러 정점과 간선이 있다고 가정해 봅시다:

# 복잡한 그래프 정의
complex_graph = {
    'A': {'B': 4, 'H': 8},
    'B': {'A': 4, 'C': 8, 'H': 11},
    'C': {'B': 8, 'D': 7, 'F': 4, 'I': 2},
    'D': {'C': 7, 'E': 9, 'F': 14},
    'E': {'D': 9, 'F': 10},
    'F': {'C': 4, 'D': 14, 'E': 10, 'G': 2},
    'G': {'F': 2, 'H': 1, 'I': 6},
    'H': {'A': 8, 'B': 11, 'G': 1},
    'I': {'C': 2, 'G': 6}
}

mst_complex, total_weight_complex = prim(complex_graph, 'A')
print("복잡한 그래프의 최소 신장 트리:", mst_complex)
print("총 가중치:", total_weight_complex)
    

결과 해석

이 복잡한 그래프의 경우, 최소 신장 트리를 구하기 위해 반복적인 선택이 필요합니다. 프림 알고리즘은 최적의 간선을 선택하여 트리를 구축하는 데 있어 효과적입니다. 실행 결과에 따라 최종 최소 신장 트리와 그 총 가중치를 출력합니다.

결론

최소 신장 트리는 네트워크 설계 및 최적화 문제에서 중요한 역할을 합니다. 본 강좌를 통해 프림 알고리즘을 파이썬으로 구현해보고, 이를 실제 문제에 적용해볼 수 있었습니다. 다양한 테스트 케이스를 통해 알고리즘의 정확성을 검증하는 것도 중요한 과정입니다. 알고리즘을 활용한 문제 풀이를 통해 코딩 테스트를 준비하는 데 도움이 되길 바랍니다!

추가적인 학습 자료

프림 알고리즘 외에도 크루스컬 알고리즘과 같은 다른 방법들을 알아보는 것도 좋습니다. 알고리즘의 이해를 돕기 위한 자료는 다음과 같습니다:

• GeeksforGeeks – Minimum Spanning Tree
• Khan Academy – Prim’s Algorithm

1. 최소 신장 트리란?

최소 신장 트리(Minimum Spanning Tree, MST)는 연결 그래프에서 모든 정점을 포함하면서
간선의 가중치의 합이 최소가 되는 부분 그래프입니다. 즉, 최소 신장 트리는 주어진 그래프에서
사이클을 형성하지 않으면서 전체 최소 비용으로 연결되는 트리를 찾는 과정입니다.

2. 문제 설명

다음은 최소 신장 트리 문제입니다:

주어진 n개의 도시와 m개의 도로에 대한 정보가 주어질
때, 모든 도시를 최소한의 비용으로 연결하는 도로의 비용의 최솟값을 구하세요.

입력 형식: 첫 번째 줄에 두 정수 n (도시의 수)와 m (도로의 수)이 주어집니다.
다음 m개의 줄에는 각 도로에 대한 정보를 나타내는 세 정수 a, b, c가 주어지며,
이는 도시 a와 도시 b를 연결하는 도로의 비용이 c임을 의미합니다.

3. 접근법

최소 신장 트리 문제를 해결하기 위해서는 일반적으로 두 가지 알고리즘을 많이 사용합니다:

• 프림(Prim) 알고리즘
• 크루스칼(Kruskal) 알고리즘

이번 글에서는 크루스칼 알고리즘을 사용하여 문제를 해결해 보겠습니다.

3.1 크루스칼 알고리즘

크루스칼 알고리즘은 다음과 같은 단계로 진행됩니다:

1. 모든 간선을 가중치(비용)에 따라 오름차순으로 정렬한다.
2. 가장 작은 간선부터 시작해 선택한다. 선택한 간선이 사이클을 형성하지 않는다면 MST에 포함시킨다.
3. 모든 간선을 검사할 때까지 2번 과정을 반복한다.

4. 알고리즘 구현

이제 위의 문제를 해결하기 위한 크루스칼 알고리즘의 파이썬 구현을 시작하겠습니다.

class DisjointSet:
    def __init__(self, n):
        self.parent = list(range(n + 1))
        self.rank = [0] * (n + 1)

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

    def union(self, u, v):
        root_u = self.find(u)
        root_v = self.find(v)

        if root_u != root_v:
            if self.rank[root_u] > self.rank[root_v]:
                self.parent[root_v] = root_u
            elif self.rank[root_u] < self.rank[root_v]:
                self.parent[root_u] = root_v
            else:
                self.parent[root_v] = root_u
                self.rank[root_u] += 1
    

4.1 입력 및 간선 정렬

입력으로 도시의 수와 도로 정보를 받아오고, 간선을 가중치에 따라 정렬합니다.

import sys

def main():
    input = sys.stdin.readline
    n, m = map(int, input().split())
    edges = []

    for _ in range(m):
        a, b, c = map(int, input().split())
        edges.append((c, a, b))

    edges.sort()  # 가중치 오름차순 정렬
    

4.2 크루스칼 알고리즘 적용

정렬된 간선들을 하나씩 확인하면서 MST를 구성합니다.

    ds = DisjointSet(n)
    mst_cost = 0

    for cost, a, b in edges:
        if ds.find(a) != ds.find(b):  # 사이클 확인
            ds.union(a, b)
            mst_cost += cost

    print(mst_cost)  # 최소 신장 트리 비용 출력
if __name__ == "__main__":
    main()
    

5. 결론

이번 글에서는 최소 신장 트리의 개념과 크루스칼 알고리즘을 통해 문제를 해결하는 방법을
알아보았습니다. 여러분도 주어진 문제를 자신만의 방식으로 분석하고 해결할 수 있는 능력을
키우길 바랍니다.

본글에서는 ‘최소 공통 조상(LCA; Lowest Common Ancestor)’ 구하기 문제 중 하나인 ‘최소 공통 조상 구하기 2’에 대해
탐구해보겠습니다. 이 문제는 특정 트리 구조에서 두 노드의 최소 공통 조상을 찾는 문제로,
특히 이진 트리에서 이루어집니다. LCA 문제는 트리 탐색 및 조작과 관련된 기본적인 문제로,
코딩 인터뷰 및 알고리즘 경시대회에서도 자주 등장합니다.

문제 설명

주어진 이진 트리가 있을 때, 두 노드 u와 v의 최소 공통 조상을 찾아야 합니다.
이진 트리는 각 노드가 최대 2개의 자식을 가질 수 있으며, 루트 노드부터 시작하여
각각의 노드는 고유한 값을 가집니다.

입력 형식

• 첫 번째 줄: 노드의 수 n (1 ≤ n ≤ 100,000)
• 두 번째 줄: 트리의 구성 (부모 노드와 자식 노드가 주어짐)
• 세 번째 줄: 두 개의 노드 u, v

출력 형식

노드 u와 v의 최소 공통 조상을 출력합니다.

예제

입력:
7
1 2
1 3
2 4
2 5
3 6
3 7
4 5

출력:
2

문제 접근 방법

이 문제를 해결하기 위해, 먼저 트리를 구성해야 합니다. 트리를 배열로 표현하거나 연결 리스트로 표현할 수 있지만,
연결 리스트를 사용하는 것이 더 효율적입니다. 이후 DFS(Depth First Search)를 통해 각 노드의 깊이를 기록하고,
부모 노드를 저장하여 이후 LCA를 쉽게 찾을 수 있습니다.

트리 구성

주어진 간선 정보를 바탕으로 노드와 자식 관계를 설정합니다.
파이썬의 딕셔너리를 사용하여 부모-자식 관계를 저장합니다.

from collections import defaultdict

def build_tree(edges):
    tree = defaultdict(list)
    for parent, child in edges:
        tree[parent].append(child)
    return tree

DFS를 통한 깊이 및 부모 노드 정보 저장

def dfs(tree, node, parent, depth, depths, parents):
    depths[node] = depth
    parents[node] = parent
    for child in tree[node]:
        if child != parent:
            dfs(tree, child, node, depth + 1, depths, parents)

LCA 함수 구현

깊이를 기준으로 두 노드의 위치를 맞춘 후, 그들의 부모를 따라 올라가면서
두 노드가 같은 노드에 도달할 때까지 진행합니다.

def lca(u, v, depths, parents):
    # Depth 맞추기
    if depths[u] < depths[v]:
        u, v = v, u

    while depths[u] > depths[v]:
        u = parents[u]

    while u != v:
        u = parents[u]
        v = parents[v]

    return u

전체 코드

def main():
    n = int(input())
    edges = [tuple(map(int, input().split())) for _ in range(n - 1)]
    u, v = map(int, input().split())

    tree = build_tree(edges)
    depths = {}
    parents = {}

    # DFS를 통해 깊이와 부모 정보 수집
    dfs(tree, 1, -1, 0, depths, parents)

    # 최소 공통 조상 찾기
    ancestor = lca(u, v, depths, parents)
    print(ancestor)

if __name__ == "__main__":
    main()

시간 복잡도

위의 알고리즘의 시간 복잡도는 O(n)입니다. 트리를 구성하고 탐색하는 과정에서
각 노드를 한 번씩 방문하기 때문입니다.

결론

‘최소 공통 조상 구하기 2’ 문제는 이진 트리의 탐색 및 조작의 기초를 이해하는 데 도움이 되며,
실제로 유용한 알고리즘입니다. 이 문제를 해결하는 과정에서 트리의 구조와 DFS의 개념을 깊이 있게 이해할 수 있게 됩니다.
이 알고리즘은 이후 다양한 문제들로 확장 가능하며, 다른 자료구조와의 응용에도 큰 도움이 됩니다.

안녕하세요! 이번 글에서는 경로 탐색 문제를 기반으로 한 “최소 비용 구하기” 알고리즘 문제를 다루어 보겠습니다. 코딩 테스트는 IT 기업에서의 취업을 위해 필수적으로 준비해야 할 요소 중 하나입니다. 문제를 해결하기 위한 전략, 알고리즘 이해, 그리고 구현 능력을 기르기 위해 이 글을 통해 단계별로 문제를 풀이해보겠습니다.

문제 설명

최소 비용을 구하는 문제는 주어진 그래프에서 출발점에서 도착점으로 가는 비용의 최솟값을 구하는 문제입니다.
아래와 같은 그래프를 예로 들어봅시다.

    1 --> 2 (비용: 4)
    1 --> 3 (비용: 2)
    2 --> 3 (비용: 1)
    2 --> 4 (비용: 5)
    3 --> 4 (비용: 8)
    

위 그래프에서 1번 노드에서 4번 노드로 가는 최소 비용을 구하시오.

입력 형식

• 첫째 줄에 노드의 수 N과 간선의 수 M (1 ≤ N ≤ 1000, 1 ≤ M ≤ 10^4)가 주어진다.
• 둘째 줄부터 M개의 줄에 각 간선의 정보가 “u v c” 형식으로 주어진다 (u, v는 노드 번호, c는 비용).
• 마지막 줄에 출발 노드와 도착 노드가 주어진다.

출력 형식

출발 노드에서 목표 노드로 가는 최소 비용을 출력하시오. 경로가 없을 경우 -1을 출력하시오.

문제 접근 방법

이 문제는 그래프의 최단 경로를 구하는 전형적인 문제로, Dijkstra 알고리즘을 사용할 것입니다. Dijkstra 알고리즘은 가중치가 있는 그래프에서 최단 경로를 찾는 데 매우 효율적입니다. 다음과 같은 단계를 통해 알고리즘을 구현할 것입니다.

1. 입력받기: 노드, 간선 정보를 입력합니다.
2. 그래프 구조화: 입력받은 간선 정보를 기반으로 그래프를 연결 리스트 형태로 표현합니다.
3. 우선순위 큐 초기화: 현재 노드에서 인접한 노드의 비용을 관리하기 위해 우선순위 큐를 설정합니다.
4. Dijkstra 알고리즘 수행: 큐에서 가장 낮은 비용의 노드를 꺼내어 인접한 노드로 가는 비용을 업데이트합니다.
5. 결과 출력: 목적지에 도달 가능한지 확인하고, 최소 비용을 출력합니다.

코드 구현

import sys
import heapq

def dijkstra(start, goal, graph, n):
    # 비용 테이블 초기화
    INF = float('inf')
    distance = [INF] * (n + 1)
    distance[start] = 0
    queue = []
    heapq.heappush(queue, (0, start))  # (비용, 노드)

    while queue:
        current_cost, current_node = heapq.heappop(queue)

        # 현재 비용이 기존의 최소 비용보다 크면 무시
        if current_cost > distance[current_node]:
            continue

        for neighbor, cost in graph[current_node]:
            new_cost = current_cost + cost

            # 인접 노드의 비용 업데이트
            if new_cost < distance[neighbor]:
                distance[neighbor] = new_cost
                heapq.heappush(queue, (new_cost, neighbor))

    return distance[goal] if distance[goal] != INF else -1

if __name__ == '__main__':
    n, m = map(int, sys.stdin.readline().strip().split())
    graph = [[] for _ in range(n + 1)]

    for _ in range(m):
        u, v, c = map(int, sys.stdin.readline().strip().split())
        graph[u].append((v, c))

    start, goal = map(int, sys.stdin.readline().strip().split())
    result = dijkstra(start, goal, graph, n)
    print(result)

코드 설명

위 코드는 Python에서 Dijkstra 알고리즘을 구현한 것입니다. 입력 파라미터로 시작 노드, 도착 노드, 그래프 구조, 총 노드의 수를 받습니다.

– 비용 테이블 초기화: 노드 수 만큼의 무한대를 가지는 리스트를 초기화합니다. 출발 노드의 비용만 0으로 설정합니다.

– 우선순위 큐 사용: Python의 힙 기능인 heapq를 활용하여 가장 낮은 비용의 노드를 처리합니다.

– 인접 노드 업데이트: 현재 노드와 인접한 노드를 순회하며 최적 비용으로 업데이트합니다.

실행 예시

입력
4 5
1 2 4
1 3 2
2 3 1
2 4 5
3 4 8
1 4

출력
6

이 예시에서는 1번 노드에서 4번 노드로 가는 최소 비용이 6임을 보여줍니다.

그리드 그래프에서의 최소 비용 구하기

위의 문제는 일반적인 그래프이지만, 2D 그리드에서의 최소 비용을 구하는 문제도 있습니다. 아랫부분에서는 2D 배열을 통해 최소 비용을 구하는 방식에 대해 설명하겠습니다.

문제 2: 그리드에서의 최소 비용 구하기

주어진 2D 배열에서 출발점 (0, 0)에서 도착점 (n-1, m-1)까지 이동할 때의 최소 비용을 구해야 합니다. 각 칸의 값은 이동할 때의 비용입니다. 상하좌우로만 이동할 수 있습니다.

입력 형식

3 3
1 2 3
4 1 2
1 5 3

주어진 배열은 다음과 같습니다:

1  2  3
4  1  2
1  5  3

출력 형식

출발점에서 목표점으로 가는 최소 비용을 출력하시오.

문제 접근 방법

이 문제는 다이나믹 프로그래밍을 사용하여 해결할 수 있습니다. 각 칸에서 최소 비용을 계산하여 이전 칸에서 도달할 수 있는 최소 비용을 업데이트하는 방식입니다.

코드 구현

def min_cost_in_grid(grid):
    n = len(grid)
    m = len(grid[0])
    dp = [[0] * m for _ in range(n)]
    dp[0][0] = grid[0][0]
    
    for i in range(n):
        for j in range(m):
            if i == 0 and j == 0:
                continue
            up = dp[i-1][j] if i > 0 else float('inf')
            left = dp[i][j-1] if j > 0 else float('inf')
            dp[i][j] = grid[i][j] + min(up, left)

    return dp[n-1][m-1]

if __name__ == '__main__':
    grid = [
        [1, 2, 3],
        [4, 1, 2],
        [1, 5, 3]
    ]
    result = min_cost_in_grid(grid)
    print(result)

코드 설명

위 코드는 2D 배열의 최소 비용을 구하는 방법을 보여줍니다. dp 배열을 통해 각 칸의 최소 비용을 저장하며, 왼쪽 또는 위쪽에서 오는 비용을 비교하여 현재 칸의 최소 비용을 설정합니다.

실행 예시

출력
8

이 예시에서는 (0, 0)에서 (2, 2)로 가는 최소 비용이 8임을 보여줍니다.

결론

이 글에서는 최소 비용 문제를 해결하기 위한 다양한 접근 방법과 알고리즘을 살펴보았습니다. Dijkstra 알고리즘을 사용한 그래프 문제와 다이나믹 프로그래밍을 활용한 그리드 문제를 통해 코딩 테스트 준비에 도움이 되었기를 바랍니다. 문제 해결 능력을 키우기 위해 다양한 문제에 도전해 보세요!

모든 과정에서 궁금한 점이나 추가적인 질문이 있으시면 댓글로 남겨 주세요. 감사합니다!