# 다익스트라

31개의 포스트
post-thumbnail

[알고리즘] 최단 경로

최단 경로 문제의 유형과 기반 지식을 알아보자

2020년 11월 19일
·
0개의 댓글
post-thumbnail

다익스트라 알고리즘(Dijkstra Algorithm)

다익스트라 알고리즘과 백준 1753번

2020년 11월 16일
·
0개의 댓글

[BOJ] 14496번 그대, 그머가 되어 c++

https://www.acmicpc.net/problem/14496 >문제 선린에 합격한 대호에게는 큰 고민이 있다. 대호는 중학교 3년 내내 공부만 했기 때문에, 요즘 학생들이 사용하는 ‘야민정음’에 대해서는 문외한이다. 친구들의 대화에 끼고 싶은 대호는 야민정음을

2020년 11월 2일
·
0개의 댓글

[백준] 1916번. 최소비용 구하기

N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터

2020년 10월 30일
·
0개의 댓글

[백준] 1753번. 최단 경로

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에

2020년 10월 30일
·
0개의 댓글

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

최단경로 > 두 노드를 잇는 가장 짧은 경로를 찾는 것. 가중치 그래프에서는 '간선의 가중치 합'이 최소가 되도록 하는 경로를 찾아야 한다. 종류) 단일 출발 및 단일 도착 (하나의 노드에서 다른 하나의 노드까지의 최단 경로) 단일 출발 최단 경로 (특정 노드와 그

2020년 10월 27일
·
0개의 댓글

최단 경로

최단 경로 탐색에 대해서 알아보고자 한다.참고 :동빈나 유튜브 채널을 기반으로 정리한 것으로, 유튜브 링크를 첨부 하겠습니다.동빈나 유튜브 링크케이스가 다양한 경우가 있다. 한 지점에서 다른 한 지점이나, 다른 모든 지점에 대한 최단 경로 찾기 -> 다익스트라모든 지점

2020년 10월 6일
·
0개의 댓글

최단경로 - (1) 다익스트라(Dijkstra) 알고리즘

다익스트라 알로리즘은 그래프에서 최단 경로를 찾는 알고리즘 중 하나로, 하나의 출발점을 기준으로 다른 모든 정점까지의 최단 거리를 구할 때를 활용할 수 있는 알고리즘이다. 다익스트라 알로리즘은 최단 거리를 찾기 위해 시작 정점에서부터 인접한 정점들을 하나씩 방문하며 해

2020년 10월 3일
·
0개의 댓글

[Python] 백준 2665

https://www.acmicpc.net/problem/2665다익스트라 알고리즘을 이용하면 쉽게 풀 수 있다.검은방을 흰방으로 바꾸는 횟수를 최소화 해야되기 때문에 다익스트라를 이용한다검은방을 방문할 경우 cnt의 값을 1씩 증가시켜 힙에 넣어주게된다면 반

2020년 9월 30일
·
0개의 댓글

배달 (python)

다익스트라 기본 문제

2020년 9월 25일
·
0개의 댓글

그래프 알고리즘

최단경로 [다익스트라], 최소신장 트리[크루스칼, 프림] + union/find 정리

2020년 9월 4일
·
0개의 댓글
post-thumbnail

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

다익스트라 알고리즘밸만포드 알고리즘플로이드-와샬 알고리즘최단경로를 찾는 알고리즘 중 다익스트라는 오직 양의 가중치를 가진 그래프만을 취급한다. 또한 특정 출발위치에서 도착위치의 최단경로를 찾는 알고리즘으로, 모든 경로의 최단경로를 구하지 않는다.그리디하게 정점을 선택하

2020년 8월 27일
·
0개의 댓글

백준 1162 Java

https://www.acmicpc.net/problem/1162다익스트라 응용 문제이다.정답 list를 1차원이 아니라 K개 만큼 도로를 없앨 수 있으므로K 크기 만큼 2차원으로 만들어서 풀어야 한다.일반적으로 PriorityQueue에 넣는 것 (포장 안하

2020년 8월 15일
·
0개의 댓글

백준 1854 Java

https://www.acmicpc.net/problem/1854다익스트라 응용 문제이다.가장 최소값이 아니라 K 번째 최소값 이기 때문에 노드의 최소값을 담는 방식을 일반 배열이 아니라K 크기의 Priority Queue 배열로 사용해야한다.방문할때마다 1)

2020년 8월 15일
·
0개의 댓글

[코딩테스트]백준 - 최단경로(1753)

최단경로(1753)입력으로 들어오는 데이터 개수가 많기 때문에 힙을 사용하지 않으면 시간초과가 난다. 최소 힙을 구현한다. 비용에 따라 배치한다. 부모노드는 자식노드보다 비용이 더 작다.최단거리 테이블을 만든다. 힙에서 값을 하나씩 빼며 거리를 계산한다. 가장 먼저,

2020년 8월 12일
·
0개의 댓글
post-thumbnail

[제대로알고리즘]다익스트라

참고 : BaaaaaaaarkingDog | \[실전 알고리즘] 0x14강 - 다익스트라 알고리즘\_구버전다익스트라 알고리즘 구현하다 스스로 얼마나 부족한지 깨달아서 새로 공부한다. 백준 최단경로(1753) 문제를 다시 풀어보며 제대로 내것으로 만들어보자 !방향 혹은

2020년 8월 10일
·
0개의 댓글

백준 11779 Java

https://www.acmicpc.net/problem/11779아래 풀었던 1916 문제에서 https://www.acmicpc.net/problem/1916최소 경로 및 길이 까지 출력해야한다.배열을 하나 더 만들어서노드를 최소 비용값으로 갱신할

2020년 8월 8일
·
0개의 댓글

백준 1916 Java

알고리즘 설명 다익스트라는 그래프에서 최소 비용을 구하는 알고리즘이다. route 값이 양의 가중치 일때만 사용가능하다. 탐색을 하면서 현재까지 비용 + 이동 비용 < 이동 할 노드의 비용 이면 이동을 하면서 내가 갈 노드 비용을 update

2020년 8월 8일
·
0개의 댓글
post-thumbnail

[알고리즘] 다익스트라

다익스트라 알고리즘 하나의 정점에서 다른 모든 정점 간의 각각 가장 짧은 거리를 구하는 문제 1) 다익스트라 알고리즘 로직 첫 정점을 기준으로 연결되어 있는 정점들을 추가해 가며, 최단 거리를 갱신하는 기법 다익스트라 알고리즘은 너비우선탐색(BFS)와 유사 첫 정

2020년 6월 22일
·
0개의 댓글