# dijkstra

231개의 포스트
post-thumbnail

우선순위 큐 (Priority Queue)

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

2일 전
·
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개의 댓글
·

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

다익스트라 알고리즘은 그래프에서 한 정점에서 다른 정점까지의 최단 경로를 구하는 알고리즘.이 과정에서 도착 정점 뿐만 아니라 모든 다른 정점까지 최단 경로로 방문하여 각 정점까지의 최단 경로로 모두 찾는다.

2023년 2월 10일
·
0개의 댓글
·
post-thumbnail

BOJ 2665 : 미로만들기

BOJ 2665 : 미로만들기

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

[백준 4485] 녹색 옷 입은 애가 젤다지? (다익스트라, 자바스크립트)

[녹색 옷 입은 애가 젤다지(https://www.acmicpc.net/problem/4485) 문제 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된

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

[백준 13549] 숨바꼭질 3 (BFS/다익스트라, 자바스크립트)

숨바꼭질 3수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는

2023년 2월 9일
·
0개의 댓글
·
post-thumbnail

프로그래머스-2022 KAKAO TECH INTERNSHIP(코딩 테스트 공부)

프로그래머스 2022 KAKAO TECH INTERNSHIP Level 3 문제 코딩 테스트 공부를 Java를 이용해 풀어보자

2023년 1월 30일
·
0개의 댓글
·

백준 6118 숨바꼭질

재서기는 수혀니와 교외 농장에서 숨바꼭질을 하고 있다. 농장에는 헛간이 많이 널려있고 재서기는 그 중에 하나에 숨어야 한다. 헛간의 개수는 N(2 <= N <= 20,000)개이며, 1 부터 샌다고 하자.재서기는 수혀니가 1번 헛간부터 찾을 것을 알고 있다.

2023년 1월 28일
·
0개의 댓글
·

백준 1238 파티

N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비

2023년 1월 27일
·
0개의 댓글
·