전체태그 보기

#다익스트라 (7개의 포스트)

doontagi
image.png 문제 파악 두 선수의 기록 시간이 동일하면서 최소 시간으로 운동 종목을 선택하는 문제이다. 종목을 선택하는 것을 간선으로 보는 것을 제외하고선, 그래프로 보는 사고가 생각나지 않아 해결하지 못했다. 문제 풀이 문제 풀이의 핵심은 이 전에 풀었던 문제인 어린이날 문제와 유사하다. 어린이날 문제는 간선을 선택으로 정점을 나...
doontagi
image.png 문제 파악 최단 거리를 구하는 문제지만 특이한 조건들로 인해 간단히 접근할 수 없다. 먼저 정점들이 소방서, 불난 곳, 불나지 않은 곳으로 나뉘어져 있다. 불난 곳들과 소방서 사이의 최단 거리를 구해야 한다. 따라서 정점마다 가장 가까운 소방서가 다르고 이에 따라 다익스트라 알고리즘을 여러번 돌리는 과정이 필요하게 되어 시간 제...
doontagi
image.png 문제 풀이 다익스트라 알고리즘의 새로운 간선의 가중치를 더하는 부분을 곱하기로 바꿔주면 된다. 이 때 우선순위 큐의 초기값으로 0이 아닌 1 또는 -1을 넣어줘야 하는 것을 주의 해야 한다. 초기값이 0이 아니라 노이즈가 없는 경우 1이기 때문이다. 느낀점 복잡한 소수점 계산의 경우 long double 형을 사용할 ...
doontagi
다익스트라 알고리즘이란 다익스트라 알고리즘은 그래프의 정점들 사이에 가중치가 주어졌을 때 한 정점에서 다른 정점으로 가는 최단 경로를 구하는 알고리즘이다. 다익스트라를 비롯한 대부분의 최단 거리 알고리즘은 음수 가중치를 갖는 간선이 있는 경우 음수 싸이클을 돌면서 가중치의 총합을 발산하는 경로가 생길 수 있어서 최단 거리를 계산할 수 없다. 다익...
백준 1719 택배
skyepodium

백준 1719 택배

2019년 2월 24일0개의 댓글
문제 - n개의 정점, m개의 간선이 주어집니다. - 간선의 정보는 1) 시작 점, 2) 도착 점, 3) 가중치 입니다. 간선의 양방향입니다. - 사진과 같이 시작 정점에서 다른 정점으로 최단 경로로 가기 위해 첫번째로 경유하는 정점들을 경로표로 출력하세요. -n(1 = n = 200) 정점의 수, m(1 = m = 10000) 간선의 수 - 시간 제한 2...
skyepodium

programmers 배달

2019년 1월 27일0개의 댓글
링크 세줄 요약 - 한 정점에서 모든 정점으로의 최단거리를 구해야한다. - 모든 간선의 가중치가 양수이다. - 위 두 조건을 만족하는 최단 경로를 알고리즘은 다익스트라 알고리즘이다.
[알고리즘] Dijkstra in python3
leejh3224

[알고리즘] Dijkstra in python3

2018년 11월 15일0개의 댓글
파이썬의 heapq 모듈을 이용해서 직접 priority queue를 구현해서 사용했고, 그래프를 그리기 위해 networkx 모듈을 사용했습니다. (코드를 돌려보시려면 설치하셔야 됩니다!) 강의는 링크에서 들으실수 있습니다.