# dijkstra
우선순위 큐 (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] 다익스트라 알고리즘
해당 글은 바킹독님의 강의를 참고해서 정리한 글입니다.하나의 시작점으로부터 다른 모든 정점까지의 최단 거리 (최소 비용)를 구하는 알고리즘. 단, 음수의 가중치를 가지는 간선이 존재하면 사용할 수 없다. 해당 경우는 벨만 포드 알고리즘 사용할 것 !다익스트라 알고리즘은
다익스트라(dijkstra) 알고리즘
다익스트라 알고리즘은 그래프에서 한 정점에서 다른 정점까지의 최단 경로를 구하는 알고리즘.이 과정에서 도착 정점 뿐만 아니라 모든 다른 정점까지 최단 경로로 방문하여 각 정점까지의 최단 경로로 모두 찾는다.
[백준 4485] 녹색 옷 입은 애가 젤다지? (다익스트라, 자바스크립트)
[녹색 옷 입은 애가 젤다지(https://www.acmicpc.net/problem/4485) 문제 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된
[백준 13549] 숨바꼭질 3 (BFS/다익스트라, 자바스크립트)
숨바꼭질 3수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는
2/4 (Sat): 코딩테스트 알고리즘 공부
Binary Sarch, Dinamic Programming, Kruskal Algorithm, Topology Sort, Cycle, Dijkstra, Floyd Warshall, Parametric Search, Disjoint Set
프로그래머스-2022 KAKAO TECH INTERNSHIP(코딩 테스트 공부)
프로그래머스 2022 KAKAO TECH INTERNSHIP Level 3 문제 코딩 테스트 공부를 Java를 이용해 풀어보자
백준 6118 숨바꼭질
재서기는 수혀니와 교외 농장에서 숨바꼭질을 하고 있다. 농장에는 헛간이 많이 널려있고 재서기는 그 중에 하나에 숨어야 한다. 헛간의 개수는 N(2 <= N <= 20,000)개이며, 1 부터 샌다고 하자.재서기는 수혀니가 1번 헛간부터 찾을 것을 알고 있다.
백준 1238 파티
N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비