목록CS (18)

하루살이 개발자

[알고리즘] 우선순위 큐 (Priority Queue)

1. 우선순위 큐란? - 일반적인 큐(Queue)는 First in-First Out 구조이다. (부가적인 조건 없이 먼저 들어온 데이터가 먼저 나가는 구조) - 우선순위 큐(Priority Queue)는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 것이다. - 우선순위 큐는 힙(Heap)이라는 자료구조를 가지고 구현할 수있다. - 큐나 스택과 비슷한 자료형이지만, 각 원소들은 우선순위를 가지고 있다. - 우선순위 큐에서, 높은 우선순위를 가진 원소는 낮은 우선순위를 가진 원소보다 먼저 처리된다. 같은 우선순위를 가진다면, 먼저 들어온 원소를 처리한다. - 우선순위 큐는 힙(heap)이라는 자료 구조를 통해 구현할 수 있다. - 우선순위 큐는 최소한 두 가지 연산이 지원되어야 한다. 하나..
CS/알고리즘 2022. 2. 16. 13:31
[알고리즘] 최단 경로 알고리즘(1) - 다익스트라(Dijkstra) 알고리즘

최단 경로 알고리즘이란, 주어진 노드와 간선(edge)들 중, 가장 짧은 경로를 찾는 알고리즘입니다. 즉, 서울에서 인천, 대전, 광주, 부산을 갈 수 있는 가장 짧은 경로를 찾는 것입니다. 0. 최단 경로 문제 - 다익스트라 알고리즘 이용(BFS 너비 우선 탐색) - "우선 순위 큐( 최소 힙 방식)"을 이용하여, 시간 복잡도 O(nlogn) - 이동경로가 양수라 하면 Dijkstra 알고리즘, 음수를 포함한다면 Bellman-ford 알고리즘 사용! * 다익스트라 알고리즘 1. 출발 노드를 설정 2. 최단 거리 테이블을 초기화(그러므로 최단 거리를 기록할 테이블을 정의해야 함) 3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택(방문하지 않은 노드를 체크해야 하므로 이를 위한 테이블을..
CS/알고리즘 2022. 2. 13. 09:26
이전 Prev 1 ··· 5 6 7 8 9 Next 다음