# dijkstra

240개의 포스트
post-thumbnail

[BOJ/C++]1238(파티)

왕복 Dijkstra

6일 전
·
0개의 댓글
·
post-thumbnail

[알고리즘] 최단 경로 알고리즘 - 다익스트라

다익스트라 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘으로 에지는 모두 0이상의 양수여야 한다.시간복잡도: O(ElogV) V(노드 수) E(에지 수)그래프를 인접 리스트로 구현한다.최단 거리 리스트를 만들고 출발 노드는 문제에 주어진대로 설정하지만 여기선 출발

2023년 5월 18일
·
0개의 댓글
·
post-thumbnail

[Algorithm] 데이크스트라 알고리즘

꼭짓점 간의 최단 경로를 찾는 알고리즘 Dijkstra. 시간복잡도, 동작방식, 예시, 우선순위큐를 활용한 구현

2023년 5월 3일
·
0개의 댓글
·
post-thumbnail

배달

heapq를 사용한 dijstra 알고리즘을 통해 최소 거리 계산

2023년 5월 1일
·
0개의 댓글
·
post-thumbnail

[Baekjoon / Python] 14938번 : 서강그라운드

14938번 : 서강그라운드

2023년 4월 30일
·
0개의 댓글
·
post-thumbnail

[코테] 알고리즘 다익스트라(Dijkstra) 최단 경로 알고리즘

알고리즘 이름 그대로 가장 짧은 거리를 찾는 알고리즘이다. 최단 경로를 탐색해야 하는 유형의 문제는 다양하게 주어지는데, 모든 지점에서 모든 지점으로의 최단 거리 구하기나 한 특정 지점에서 모든 지점으로의 최단거리 혹은, 어느 특정 지점에서 한 특정 지점으로의 최단거리

2023년 4월 29일
·
0개의 댓글
·
post-thumbnail

알고리즘 강의 정리 10 : 다익스트라 알고리즘

다익스트라 알고리즘은 그래프의 두 정점 사이에 존재하는 최단 경로를 찾는 것.다익스트라 알고리즘은 다익스트라 최단 경로 알고리즘의 줄임말이다그리디 알고리즘의 일종.다익스트라 알고리즘은 그래프에 대해 작동한다.코딩을 할때 우선순위 큐를 사용한다정점들을 연결하는 간선에 길

2023년 4월 6일
·
0개의 댓글
·

BOJ 1753 PS일기 - dijkstra

요구사항 O(ElgE)의 시간복잡도로 모든 정점까지 그래프 최단경로를 찾아야한다. V : 정점(노드)의 갯수 E : 간선의 갯수 문제접근 힙을 이용한 최소비용의 경로를 우선순위로 연산하여 노드가 2만개까지 대량으로 주어줘도 빠르게 찾을 수 있도록 목표를 잡았다.

2023년 4월 6일
·
0개의 댓글
·
post-thumbnail

우선순위 큐 (Priority Queue)

우선순위 큐 모든 데이터에 우선 순위가 있음 우선순위가 높은 데이터가 먼저 나옴 (선입선출 FIFO가 아님) Dequeue시, 우선순위가 높은 순으로 나감 우선순위가 에는 선입선출 PriorityQueue클래스를 이용하여 우선순위 큐를 구현 우선순위 큐(Priorit

2023년 3월 25일
·
0개의 댓글
·
post-thumbnail

BOJ 12834 - 주간미팅

문제 https://www.acmicpc.net/problem/12834

2023년 3월 20일
·
0개의 댓글
·

백준 13549. 숨바꼭질 3 메모리 최적화를 향하여 - 데이크스트라 알고리즘을 사용한 풀이

visited 세트를 따로 만들지 않았다. 대신 딕셔너리 graph를 활용했다.그래프 키는 리스트로 만들었다. pop하면서 리스트의 크기를 줄여나가 메모리를 최적화했다.시작점으로부터 모든 노드까지 일일이 거리를 다 기록하지 않도록 작성했다.데이크스트라 알고리즘을 연습하

2023년 3월 19일
·
0개의 댓글
·
post-thumbnail

백준 9370

문제

2023년 3월 19일
·
0개의 댓글
·
post-thumbnail

백준 1504

문제1부터 N까지의 최단 거리를 구해야하고 반드시 v1과 v2를 정점으로 하는 간선을 지나야함(간선은 방향성 없음)d : v1과 v2로 이루어진 간선의 가중치따라서 1) 1부터 v1 까지 최단 거리 + v2부터 N 까지의 최단 거리2) 1부터 v2 까지 최단 거리 +

2023년 3월 17일
·
0개의 댓글
·
post-thumbnail

백준 1753

문제예제 입력을 보면먼저 1과 5가 연결되어 있지만 입력은 5 1 1로 주어지고예제 출력에서 1부터 5까지의 경로가 없다고 하니방향성이 존재한다는 것에 주의dfs로 시작 지점부터 i번 노드까지의 최단 거리를 갱신하며 disti에 저장할 예정이 때, 우선순위 큐를 쓰는데

2023년 3월 17일
·
0개의 댓글
·

[C++] 1916: 최소비용 구하기

데이크스트라

2023년 3월 9일
·
0개의 댓글
·

[알고리즘]다익스트라(dijkstra)

다익스트라(최단경로) : 지하철 노선도, 네비게이션 등 실생활에 많이 사용되는 알고리즘. graph 출발 노드와 도착 노드 설정 python에서는 dictionary 객체 이용하여 graph 표현 가능 Node Edge

2023년 3월 7일
·
0개의 댓글
·
post-thumbnail

230302 공부내용 정리

230302 공부내용 정리 용어 정리 최단 경로 알고리즘 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로 하나의 시작 정점에서 끝 정점까지의 최단 경로 다익스트라(dijkstra)알고리즘 음의 가중치를 허용하지 않음 정점 중심 해결 벨만-포드(Bellman_For...

2023년 3월 2일
·
0개의 댓글
·

[Algorithm] BOJ 4485 녹색옷입은애가젤다지?

https://www.acmicpc.net/problem/4485주어진 2차원 배열에는 각 칸에서 잃는 소지금이 적혀있다. (0,0)에서 시작해 (N-1, N-1) 위치까지 최소한의 소지금을 잃는 루트로 이동했을 때, 잃을 수 밖에 없는 소지금은 얼마인지 묻는

2023년 2월 15일
·
0개의 댓글
·

[Algorithm] 다익스트라 알고리즘

해당 글은 바킹독님의 강의를 참고해서 정리한 글입니다.하나의 시작점으로부터 다른 모든 정점까지의 최단 거리 (최소 비용)를 구하는 알고리즘. 단, 음수의 가중치를 가지는 간선이 존재하면 사용할 수 없다. 해당 경우는 벨만 포드 알고리즘 사용할 것 !다익스트라 알고리즘은

2023년 2월 14일
·
0개의 댓글
·