# dijkstra
[알고리즘] 최단 경로 알고리즘 - 다익스트라
다익스트라 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘으로 에지는 모두 0이상의 양수여야 한다.시간복잡도: O(ElogV) V(노드 수) E(에지 수)그래프를 인접 리스트로 구현한다.최단 거리 리스트를 만들고 출발 노드는 문제에 주어진대로 설정하지만 여기선 출발
[Algorithm] 데이크스트라 알고리즘
꼭짓점 간의 최단 경로를 찾는 알고리즘 Dijkstra. 시간복잡도, 동작방식, 예시, 우선순위큐를 활용한 구현
[코테] 알고리즘 다익스트라(Dijkstra) 최단 경로 알고리즘
알고리즘 이름 그대로 가장 짧은 거리를 찾는 알고리즘이다. 최단 경로를 탐색해야 하는 유형의 문제는 다양하게 주어지는데, 모든 지점에서 모든 지점으로의 최단 거리 구하기나 한 특정 지점에서 모든 지점으로의 최단거리 혹은, 어느 특정 지점에서 한 특정 지점으로의 최단거리
알고리즘 강의 정리 10 : 다익스트라 알고리즘
다익스트라 알고리즘은 그래프의 두 정점 사이에 존재하는 최단 경로를 찾는 것.다익스트라 알고리즘은 다익스트라 최단 경로 알고리즘의 줄임말이다그리디 알고리즘의 일종.다익스트라 알고리즘은 그래프에 대해 작동한다.코딩을 할때 우선순위 큐를 사용한다정점들을 연결하는 간선에 길
BOJ 1753 PS일기 - dijkstra
요구사항 O(ElgE)의 시간복잡도로 모든 정점까지 그래프 최단경로를 찾아야한다. V : 정점(노드)의 갯수 E : 간선의 갯수 문제접근 힙을 이용한 최소비용의 경로를 우선순위로 연산하여 노드가 2만개까지 대량으로 주어줘도 빠르게 찾을 수 있도록 목표를 잡았다.
우선순위 큐 (Priority Queue)
우선순위 큐 모든 데이터에 우선 순위가 있음 우선순위가 높은 데이터가 먼저 나옴 (선입선출 FIFO가 아님) Dequeue시, 우선순위가 높은 순으로 나감 우선순위가 에는 선입선출 PriorityQueue클래스를 이용하여 우선순위 큐를 구현 우선순위 큐(Priorit
백준 13549. 숨바꼭질 3 메모리 최적화를 향하여 - 데이크스트라 알고리즘을 사용한 풀이
visited 세트를 따로 만들지 않았다. 대신 딕셔너리 graph를 활용했다.그래프 키는 리스트로 만들었다. pop하면서 리스트의 크기를 줄여나가 메모리를 최적화했다.시작점으로부터 모든 노드까지 일일이 거리를 다 기록하지 않도록 작성했다.데이크스트라 알고리즘을 연습하
백준 1504
문제1부터 N까지의 최단 거리를 구해야하고 반드시 v1과 v2를 정점으로 하는 간선을 지나야함(간선은 방향성 없음)d : v1과 v2로 이루어진 간선의 가중치따라서 1) 1부터 v1 까지 최단 거리 + v2부터 N 까지의 최단 거리2) 1부터 v2 까지 최단 거리 +
백준 1753
문제예제 입력을 보면먼저 1과 5가 연결되어 있지만 입력은 5 1 1로 주어지고예제 출력에서 1부터 5까지의 경로가 없다고 하니방향성이 존재한다는 것에 주의dfs로 시작 지점부터 i번 노드까지의 최단 거리를 갱신하며 disti에 저장할 예정이 때, 우선순위 큐를 쓰는데
[알고리즘]다익스트라(dijkstra)
다익스트라(최단경로) : 지하철 노선도, 네비게이션 등 실생활에 많이 사용되는 알고리즘. graph 출발 노드와 도착 노드 설정 python에서는 dictionary 객체 이용하여 graph 표현 가능 Node Edge
230302 공부내용 정리
230302 공부내용 정리 용어 정리 최단 경로 알고리즘 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로 하나의 시작 정점에서 끝 정점까지의 최단 경로 다익스트라(dijkstra)알고리즘 음의 가중치를 허용하지 않음 정점 중심 해결 벨만-포드(Bellman_For...
[Algorithm] BOJ 4485 녹색옷입은애가젤다지?
https://www.acmicpc.net/problem/4485주어진 2차원 배열에는 각 칸에서 잃는 소지금이 적혀있다. (0,0)에서 시작해 (N-1, N-1) 위치까지 최소한의 소지금을 잃는 루트로 이동했을 때, 잃을 수 밖에 없는 소지금은 얼마인지 묻는
[Algorithm] 다익스트라 알고리즘
해당 글은 바킹독님의 강의를 참고해서 정리한 글입니다.하나의 시작점으로부터 다른 모든 정점까지의 최단 거리 (최소 비용)를 구하는 알고리즘. 단, 음수의 가중치를 가지는 간선이 존재하면 사용할 수 없다. 해당 경우는 벨만 포드 알고리즘 사용할 것 !다익스트라 알고리즘은