다익스트라

힙의 특징최단 경로를 찾을 때 널리 사용하는 다익스트라 알고리즘은, 탐색 큐의 자료구조가 전체 성능에 결정적인 영향을 미친다. 때문에 추가/삭제를 빠르게 수행할 수 있는 우선순위 큐를 주로 사용한다. 우선순위 큐는 일반 큐와 비슷하지만, 각 요소가 우선순위를 가지고 있으며, 우선순위가 높은 요소가 먼저 출력된다는 점이 다르다. 우선순위 큐는 크게 배열, 연결리스트, 힙 이렇게 세 가지 방법으로 구현할 수 있다. 그중 완전 이진 트리 구조를 갖는 힙으로 구현하면 추가/제거의 효율성이 크게 향상된다. 구현 방법삽입삭제순서 없는 배열O(1)O(n)순서 없는 연결리스트O(1)O(n)정렬된 배열O(n)O(1)정렬된 연결리스트O(n)O(1)힙O(log n)O(log n) 이진 트리는 각 부모 노드가 왼쪽/오른쪽 최..

문제 분석프로그래머스 레벨 2의 배달 문제(12978)는 마을 개수 N, 두 마을 사이의 거리 정보 road, 배달 가능한 시간(거리) K를 인자로 받아, 1번 마을에 있는 음식점이 K이하 시간에 배달할 수 있는 마을의 개수를 반환해야 한다. 마을 개수 N : 1 ≤ N ≤ 50거리 정보 : [[a, b, c], [...]]a b : 두 마을의 번호c : 두 마을의 거리(시간)배달 가능한 시간 K : 1 ≤ K ≤ 500,000 위 마을 이미지를 기준으로 1번부터 5번 마을까지 최소 배달 시간을 [번호, 시간] 배열 형태로 나타내면 아래와 같다. 만약 배달 가능한 시간 K가 3이라면 1, 2, 4, 5번 마을이 모두 3시간 이하여서 정답은 4가 된다.  이처럼 1번 마을에서 다른 모든 마을까지 소요되는 ..