반응형 우선순위 큐2 일반 다익스트라 vs. 힙을 활용한 다익스트라: 차이점과 성능 비교 다익스트라 알고리즘(Dijkstra's Algorithm)은 그래프에서 한 정점에서 다른 모든 정점까지의 최단 경로를 찾는 대표적인 알고리즘입니다. 이 알고리즘을 구현하는 방법에는 일반적인 방식(배열 기반) 과 힙(Heap)을 활용한 방식 두 가지가 있으며, 성능 차이가 매우 큽니다. 본 글에서는 두 방식의 차이점을 깊이 있게 분석하고, 성능 비교를 통해 어떤 상황에서 어떤 방법이 더 적합한지 알아보겠습니다. 1. 일반 다익스트라 알고리즘 (배열 기반)개념일반적인 다익스트라 알고리즘은 배열(Array) 또는 선형 탐색(Linear Search) 을 이용하여 최단 거리를 찾습니다.2025.02.07 - [알고리즘] - 다익스트라 알고리즘(Dijkstra's Algorithm) 총 정리 - 개념, 원리, .. 2025. 2. 22. HEAP (2) - 업그레이드 된 HEAP 힙 (특정원소 삭제, 업데이트 O(logN)만에 가능) 2023.03.12 - [자료구조/HEAP 힙] - 1.HEAP 힙 기본 구현 (C언어 구현, index 1부터 시작) 1.HEAP 힙 기본 구현 (C언어 구현, index 1부터 시작)1. HEAP 힙 요약 힙은 우선순위가 가장 높은 원소가 루트(첫번째 인덱스)에 존재하는 것이 보장된 자료구조입니다. 또한, 부모노드는 자식노드보다 우선순위가 높습니다.(우선순위가 같은 경우가best-coding.tistory.com지난 시간에 구현한 힙 코드를 조금 더 업그레이드 시켜서 특정 원소 삭제 및 업데이트가 O(logN)만에 가능한 코드를 만들어 보겠습니다. 1. 기본 아이디어지난번에는 특정 id에 해당하는 원소를 찾기위해 힙의 첫번째 원소부터 순차적으로 반복문을 돌리면서 해당하는 인덱스를 얻었습니다. 하지만.. 2023. 3. 12. 이전 1 다음 반응형
