다익스트라 알고리즘2 다익스트라 알고리즘 정리 지난 알고리즘 글에서 다익스트라 알고리즘을 정리한 글을 작성한다 예고했었다. 다익스트라 알고리즘의 구현 방법 및, 실제 문제 풀이를 정리해보고자 한다. 다익스트라 알고리즘(Dijkstra's Algorithm) : 그래프 상의 두 정점 사이의 최단거리를 구하는 알고리즘. GPS, 네트워크 라우팅 등의 다양한 분야에서 활용된다. 다익스트라 알고리즘 구현 다익스트라 알고리즘은 다음과 같은 과정을 거친다. 시작점에서 탐색을 시작한다. 새 노드에 방문할 때마다, 가장 작은 거리(가중치)를 갖는 노드를 골라서 방문한다. 방문한 노드의 각 인접점에 대해, 시작점까지의 거리를 계산한다. → 이 때, 새로운 최단거리가 나오면 최단거리를 업데이트 한다. 이전에 다른 글에서 정리한 그래프와 달리, 다익스트라 알고리즘의 구.. 2023. 12. 28. 이진 힙(Binary Heap) 정리 알고리즘 문제 풀이를 진행하다 다익스트라 알고리즘 문제를 접하게 되었다. 다익스트라 알고리즘이 유명한 알고리즘이기도 하고, 이번 기회에 다익스트라 알고리즘 구현에 잘 쓰이는 이진 힙 및 우선순위 큐에 대해 알아보는 것이 좋겠다 싶어 강의를 들은 내용을 간략히 기록한다. 강의는 Udemy에 있는 JavaScript 알고리즘 & 자료구조 마스터클래스 이다. 힙 (Heap) : 트리와 비슷한 자료구조. 다만 트리와 달리 부모와 자식 노드 사이의 관계에 대한 조건이 존재한다. 이 조건은 힙의 종류에 따라 다름. 최대 힙(Max Heap): 부모가 늘 자식보다 큰 값을 지닌다. 최소 힙(Min Heap): 부모가 늘 자식보다 작은 값을 지닌다. 이진 힙(Binary Heap) : 힙 중에서도 오직 2개의 자식 노.. 2023. 12. 19. 이전 1 다음
