그리디 알고리즘 스터디: Prim과 Dijkstra 알고리즘 이해

이번 스터디에서는 그래프 탐색 알고리즘의 핵심인 Prim과 Dijkstra 알고리즘에 대해 깊이 있게 학습했습니다. 두 알고리즘 모두 그리디(Greedy) 방식을 사용하지만, 목표와 탐색 방식에 분명한 차이가 있다는 것을 명확히 이해할 수 있었습니다.

학습 주제

• 공부 주제: 그리디 알고리즘 (Prim, Dijkstra)
• 대화 제목: 그리디 알고리즘 스터디 - Prim, Daijkstra
• 학습 날짜: 2026년 4월 16일 ~ 4월 17일

질문과 탐구

이번 학습은 슬라이드 자료를 기반으로 진행되었습니다. 주로 다음과 같은 질문들을 던지며 알고리즘의 동작 원리를 파고들었습니다.

• Prim 알고리즘에서 Y와 V-Y 집합의 의미는 무엇인가?
• nearest와 distance 배열은 각각 어떤 역할을 하는가?
• distance[i] = -1의 의미는 무엇이며, 갱신 조건은 어떻게 되는가?
• nearest[i]는 Y 집합 자체를 의미하는가?
• vnear와 nearest[vnear]의 관계는 무엇이며, 이것이 MST 간선 선택에 어떻게 사용되는가?
• Dijkstra 알고리즘에서 length와 touch 배열은 어떤 역할을 하는가?
• Prim과 Dijkstra의 갱신 조건(W[i][vnear] vs length[vnear] + W[vnear][i])의 차이는 무엇인가?
• 방향 그래프에서 Dijkstra 알고리즘의 W[vnear][i] 순서가 중요한 이유는 무엇인가?
• vnear가 Y에 편입된 후에도 갱신 루프에 사용되는 이유는 무엇인가?

핵심 학습 내용

Prim 알고리즘: 최소 비용 신장 트리(MST) 구축

Prim 알고리즘은 주어진 그래프에서 모든 정점을 최소 비용으로 연결하는 트리(MST, Minimum Spanning Tree)를 찾는 알고리즘입니다. 핵심 아이디어는 '이미 선택된 정점 집합(Y)에서, 아직 선택되지 않은 정점 집합(V-Y)으로 뻗는 가장 짧은 간선을 계속 추가하는 것' 입니다.

• 기본 개념:
  • Y: 현재까지 MST에 포함된 정점들의 집합
  • V-Y: 아직 MST에 포함되지 않은 정점들의 집합
  • nearest[i]: V-Y의 정점 i에서 가장 가까운 Y 안의 정점의 인덱스
  • distance[i]: V-Y의 정점 i와 Y 안의 nearest[i] 사이의 간선 가중치. distance[i] = -1이면 i는 이미 Y에 포함되었음을 의미합니다.
• 동작 과정:
  1. 초기화: Y에 임의의 정점(보통 v1)을 넣고, 나머지 모든 정점 i에 대해 nearest[i] = 1, distance[i] = W[1][i]로 초기화합니다. (즉, 처음에는 Y의 유일한 정점인 v1이 가장 가까운 정점으로 설정됩니다.)
  2. 반복 (n-1번):
     • V-Y의 정점 중 distance[i]가 가장 작은 vnear를 선택합니다. (가장 가까운 V-Y 정점을 찾습니다.)
     • vnear를 Y에 추가하고, vnear와 nearest[vnear]를 잇는 간선을 MST에 추가합니다. (distance[vnear]를 -1로 설정하여 방문했음을 표시합니다.)
     • 새롭게 Y에 포함된 vnear 때문에, 나머지 V-Y의 정점 i들에 대해 distance[i]를 갱신합니다. 이때, vnear를 통하는 것이 기존 distance[i]보다 짧을 경우에만 갱신합니다 (if W[i][vnear] < distance[i]:).
• 변수명 정리: 혼란을 줄이기 위해 nearest는 closest_in_Y, distance는 dist_to_Y, vnear는 new_v로 이해하면 직관적입니다.

Dijkstra 알고리즘: 단일 출발점 최단 경로 탐색

Dijkstra 알고리즘은 한 출발점에서 다른 모든 정점까지의 최단 경로를 찾는 알고리즘입니다. Prim과 유사한 구조를 가지지만, '출발점(v1)에서부터 현재 정점까지의 누적 거리' 를 관리하며 탐색합니다.

• 기본 개념:
  • Y: 현재까지 출발점(v1)으로부터의 최단 거리가 확정된 정점들의 집합
  • V-Y: 아직 최단 거리가 확정되지 않은 정점들의 집합
  • touch[i]: v1에서 i까지 최단 경로를 구성할 때, i의 바로 직전 정점
  • length[i]: v1에서 i까지 현재까지 알려진 최단 거리. length[i] = -1은 i가 Y에 포함되었음을 의미합니다.
• 동작 과정:
  1. 초기화: Y에 출발점(v1)을 넣고, 나머지 모든 정점 i에 대해 touch[i] = 1, length[i] = W[1][i]로 초기화합니다. (즉, v1에서 i까지의 직접적인 거리가 초기 최단 거리로 설정됩니다.)
  2. 반복 (n-1번):
     • V-Y의 정점 중 length[i]가 가장 작은 vnear를 선택합니다. (출발점에서 가장 가까운 V-Y 정점을 찾습니다.)
     • vnear를 Y에 추가하고, touch[vnear]와 vnear를 잇는 간선을 최단 경로에 포함시킵니다. (length[vnear]를 -1로 설정하여 방문했음을 표시합니다.)
     • 새롭게 Y에 포함된 vnear를 경유하여 다른 V-Y의 정점 i로 가는 경로가 기존 length[i]보다 짧은지 확인하고 갱신합니다 (if length[vnear] + W[vnear][i] < length[i]:). 이때 touch[i]를 vnear로 갱신하여 경로를 추적할 수 있게 합니다.
• 핵심 차이:
  • Prim: V-Y 정점이 이미 형성된 Y 집합과 얼마나 가까운지를 기준으로 다음 정점을 선택합니다. (간선 자체의 비용이 중요)
  • Dijkstra: V-Y 정점이 출발점(v1)으로부터 얼마나 멀리 있는지(누적 거리) 를 기준으로 다음 정점을 선택합니다. (경로의 총 비용이 중요)
  • 그래프가 무방향이면 Prim, 방향이면 Dijkstra를 사용하는 것이 일반적입니다. (Dijkstra는 방향 그래프에서도 잘 동작하지만, 무방향 그래프에서는 Prim이 더 효율적일 수 있습니다.)

이해한 내용

이번 학습을 통해 Prim과 Dijkstra 알고리즘의 그리디 선택 기준이 다르다는 것을 명확하게 이해했습니다.

• Prim은 현재까지 만들어진 트리의 '외곽' 에 있는 노드들 중에서, 트리에 가장 가까운 노드를 선택하여 트리를 확장하는 방식입니다. 마치 주변에서 가장 값싼 재료를 바로 가져와 조립하는 느낌입니다.
• Dijkstra는 '출발점' 에서부터 '누적 거리가 가장 짧은' 노드를 선택하여 최단 경로를 확정해 나가는 방식입니다. 마치 출발점에서 가장 가까운 곳부터 차근차근 방문하여 최단 경로를 기록해 나가는 느낌입니다.

또한, distance (Prim)와 length (Dijkstra) 배열의 역할, nearest와 touch 배열의 차이, 그리고 갱신 조건(W[i][vnear] vs length[vnear] + W[vnear][i])의 의미를 명확히 파악할 수 있었습니다. 특히 Dijkstra의 length[vnear] + W[vnear][i] 갱신이 단순히 간선 비용이 아니라 '출발점 → vnear → i' 라는 전체 경로의 누적 거리를 나타낸다는 점이 중요했습니다.

실전 적용

• 최소 비용 신장 트리: Prim 알고리즘은 네트워크 설계, 케이블링, 최소 비용으로 여러 지점을 연결해야 하는 경우 등에 활용될 수 있습니다. 예를 들어, 여러 도시를 가장 적은 비용으로 모두 연결하는 도로망을 구축할 때 사용할 수 있습니다.
• 최단 경로 찾기: Dijkstra 알고리즘은 내비게이션 시스템, 길 찾기 서비스, 네트워크 라우팅, 게임에서의 AI 경로 탐색 등 다양한 분야에서 핵심적으로 사용됩니다.
• 실습 계획:
  • Python으로 Prim 및 Dijkstra 알고리즘을 직접 구현해보고, 작은 그래프에 대해 동작을 테스트해볼 예정입니다.
  • 각 알고리즘의 시간 복잡도를 고려하여, 대규모 그래프에서의 성능을 비교 분석하는 실습을 진행해볼 계획입니다.
• 응용 아이디어:
  • Prim 알고리즘을 활용하여, 여러 개의 서버를 가장 적은 네트워크 비용으로 연결하는 방안을 설계할 수 있습니다.
  • Dijkstra 알고리즘을 응용하여, 실시간 교통 정보(도로의 통행량, 사고 등)를 반영하여 최적의 경로를 탐색하는 시스템을 구축할 수 있습니다.

추가 학습 계획

• 알고리즘 최적화: Prim 알고리즘의 경우, 우선순위 큐(Priority Queue)를 사용하면 시간 복잡도를 개선할 수 있습니다. Dijkstra 알고리즘 또한 힙(Heap)을 사용한 구현을 학습하여 효율성을 높이고 싶습니다.
• 다른 그래프 알고리즘: Kruskal 알고리즘(Prim과 함께 MST를 찾는 알고리즘), BFS(너비 우선 탐색), DFS(깊이 우선 탐색) 등 다른 기본적인 그래프 탐색 알고리즘들도 더 깊이 공부하여 그래프 알고리즘 전반에 대한 이해도를 높일 계획입니다.
• 관련 자료: 알고리즘 강의 영상, 관련 서적(예: CLRS 알고리즘 책), 온라인 코딩 플랫폼(LeetCode, Programmers 등)의 그래프 문제 풀이를 통해 실제 적용 연습을 할 예정입니다.

참고 자료

• 슬라이드 자료: Prim, Dijkstra 알고리즘 설명 (AI와의 대화를 통해 제공됨)
• AI (Claude): 알고리즘 동작 원리, 코드 설명, 질문 답변 제공
• 인접 행렬(Adjacency Matrix): W[i][j]는 정점 i와 j 사이의 간선 가중치를 나타냅니다. 방향 그래프에서는 W[i][j] != W[j][i]일 수 있습니다.