ITPE * JackerLab

개요Fibonacci Heap은 그래프 알고리즘에서 중요한 역할을 하는 우선순위 큐 구현 구조로, 특히 Decrease-Key, Merge 연산에서 탁월한 이론적 성능을 보이는 자료구조입니다. 이름은 노드 수가 피보나치 수열을 따르는 구조적 특성에서 유래하며, Dijkstra, Prim 알고리즘의 이론적 시간 복잡도를 낮추는 데 핵심 역할을 합니다.1. 개념 및 정의Fibonacci Heap은 연결 리스트 기반의 느슨한 구조로 구성된 **최소 힙(min heap)**이며, 여러 개의 트리를 루트 리스트로 구성하고 lazy 방식으로 병합 및 삽입을 처리합니다.창시자: Fredman과 Tarjan (1984)특징: 느슨한 균형 유지, 지연된 구조 조정(lazy consolidation)용도: 최단 경로 탐색..

개요다익스트라(Dijkstra) 알고리즘은 그래프 상에서 하나의 시작 정점으로부터 다른 모든 정점까지의 최단 경로를 계산하는 알고리즘이다. 가중치가 있는 그래프에서 각 정점까지의 최소 비용을 계산하며, 우선순위 큐를 사용해 탐색 효율을 극대화한다. GPS 내비게이션, 네트워크 라우팅, 교통망 분석 등 다양한 실무 분야에서 핵심적으로 사용된다. 본 글에서는 다익스트라 알고리즘의 개념, 동작 원리, 구현 방식, 시간 복잡도, 활용 사례를 체계적으로 정리한다.1. 개념 및 정의다익스트라 알고리즘은 음수 간선이 없는 가중치 그래프에서 시작 노드로부터 모든 노드까지의 최단 경로를 구하는 탐색 알고리즘이다. 각 정점까지의 거리를 지속적으로 업데이트하며, 우선순위 큐(Priority Queue)를 사용해 가장 짧은 ..