인턴으로 다닌 회사도 기간이 끝나 퇴사하고, 대학교 개강도 2주 연기되면서
학교 기숙사에서 딩굴거리고 있습니다
그러던 중에, 하루에 알고리즘 1개씩 다시 익히면 꽤 남는게 있지 않을까 싶어서
solved.ac에서 분류되어있는 알고리즘 중 오늘은 다익스트라 알고리즘을 살짝쿵 건드려봤습니다.
푼 문제들은 아래와 같습니다.
다익스트라 알고리즘을 딱 사용하고 적당히 활용하는 문제들이어서 비교적 쉽게? 푼 것 같습니다.
계속 조건만 바꿔가면서 코드를 제출했으니 말이죠.
https://www.acmicpc.net/problem/1753
1753번: 최단경로
첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두
www.acmicpc.net
https://www.acmicpc.net/problem/18352
18352번: 특정 거리의 도시 찾기
첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개의 자연수 A, B가 공백을 기준으로 구분되어 주어진다. 이는 A번 도시에서 B번 도시로 이동하는 단방향 도로가 존재한다는 의미다. (1 ≤ A, B ≤ N) 단, A와 B는 서로 다른 자연수이다.
www.acmicpc.net
https://www.acmicpc.net/problem/1446
1446번: 지름길
첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하이고, D는 10,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주어진다. 모든 위치와 길이는 10,000보다 작거나 같은 음이 아닌 정수이다. 지름길의 시작 위치는 도착 위치보다 작다.
www.acmicpc.net
https://www.acmicpc.net/problem/5972
5972번: 택배 배송
문제 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 구두쇠라서 최소한의 소들을 만나면서 지나가고 싶습니다. 농부 현서에게는 지도가 있습니다. N (1 <= N <= 50,000) 개의 헛간과, 소들의 길인 M (1 <= M <= 50,000) 개의 양방향 길이 그려져 있고, 각각의 길은 C_i (0 <= C_i <=
www.acmicpc.net
https://www.acmicpc.net/problem/17396
17396번: 백도어
첫 번째 줄에 분기점의 수와 분기점들을 잇는 길의 수를 의미하는 두 자연수 N과 M이 공백으로 구분되어 주어진다.(1 ≤ N ≤ 100,000, 1 ≤ M ≤ 300,000) 두 번째 줄에 각 분기점이 적의 시야에 보이는지를 의미하는 N개의 정수 a0, a1, ..., aN-1가 공백으로 구분되어 주어진다. ai가 0이면 i 번째 분기점이 상대의 시야에 보이지 않는다는 뜻이며, 1이면 보인다는 뜻이다. 추가적으로 a0 = 0, aN-1 = 1이다., N-
www.acmicpc.net
근데, 이번에 계속 다익스트라 알고리즘을 사용하면서도 제가 잘못된 다익스트라 알고리즘을 사용하고 있다는 것을 알았습니다. 아래 링크의 내용입니다.
http://www.secmem.org/blog/2019/01/09/wrong-dijkstra/
제가 설명하기엔 너무나 좋은 내용이고 다시 글을 정리해봤자 똑같은 내용이 될 것 같아 링크로 남깁니다.
제가 위의 링크에 있는 내용, 코드를 제 입맛에 맞춘 코드는 아래 링크에 있습니다.
https://github.com/shinkeonkim/Today_PS/blob/master/algorithm/dijkstra.cpp
shinkeonkim/Today_PS
Online Judge Site Solution. Contribute to shinkeonkim/Today_PS development by creating an account on GitHub.
github.com
'내가 공부하려고 만들어가는 목록' 카테고리의 다른 글
| [내공만목] 대충 어린이날에 푼 골드 문제들 정리 (0) | 2020.05.05 |
|---|---|
| [내공만목] 어쩌다가 knapsack 문제들을 풀게 되었다. (0) | 2020.05.03 |
| [내공만목] Convex Hull 공부하기 (0) | 2020.05.01 |
| [내공만목] erdos-ginzburg-ziv theorem && Zero sum problem (0) | 2020.04.11 |
| [내가 공부하려고 만들어가는 목록] 목표 01 (2) | 2020.04.10 |