priority queue
-
알고리즘, graph, DijkstraData Structure & Algorithm 2024. 7. 3. 18:18
다익스트라 알고리즘(Dijkstra's Algorithm)은 그래프에서 한 정점에서 다른 모든 정점으로의 최단 경로를 찾는 데 사용되는 알고리즘입니다. 이 알고리즘은 가중치가 있는 그래프에서 사용되며, 가중치가 음수가 아닌 경우에만 적용할 수 있습니다.다익스트라 알고리즘의 개념시작 정점 선택: 알고리즘은 시작 정점에서 시작합니다.최단 경로 집합: 최단 경로를 확정한 정점들의 집합을 유지합니다.미확정 집합: 아직 최단 경로가 확정되지 않은 정점들의 집합을 유지합니다.거리 배열: 시작 정점에서 각 정점까지의 현재까지 발견된 최단 거리를 저장합니다. 초기에는 시작 정점의 거리를 0으로 설정하고 나머지 정점의 거리를 무한대로 설정합니다.이웃 정점 업데이트: 현재 정점에서 인접한 정점들로의 거리를 계산하고, 더 ..
-
자료구조와 알고리즘, Tree, Priority QueueData Structure & Algorithm 2024. 6. 28. 18:21
우선순위 큐(Priority Queue)는 각 요소가 우선순위를 가지는 데이터 구조로, 일반적인 큐와 달리 요소들이 우선순위에 따라 제거됩니다. 우선순위 큐는 큐의 일종이지만, 요소를 삽입할 때 그 우선순위에 따라 적절한 위치에 배치하고, 제거할 때는 가장 높은(또는 낮은) 우선순위를 가진 요소를 먼저 제거합니다.우선순위 큐의 특징우선순위에 따른 요소 관리: 각 요소는 우선순위를 가지고 있으며, 큐의 요소는 우선순위에 따라 정렬됩니다.삽입 및 제거: 삽입 연산과 제거 연산은 모두 우선순위를 고려하여 수행됩니다.응용 분야: 작업 스케줄링, 네트워크 트래픽 관리, 시뮬레이션 시스템 등에서 자주 사용됩니다.구현 방법우선순위 큐는 다양한 방법으로 구현할 수 있지만, 가장 효율적인 방법은 힙(heap) 자료구조를..