인턴으로 다닌 회사도 기간이 끝나 퇴사하고, 대학교 개강도 2주 연기되면서
학교 기숙사에서 딩굴거리고 있습니다
그러던 중에, 하루에 알고리즘 1개씩 다시 익히면 꽤 남는게 있지 않을까 싶어서
solved.ac에서 분류되어있는 알고리즘 중 오늘은 다익스트라 알고리즘을 살짝쿵 건드려봤습니다.
푼 문제들은 아래와 같습니다.
다익스트라 알고리즘을 딱 사용하고 적당히 활용하는 문제들이어서 비교적 쉽게? 푼 것 같습니다.
계속 조건만 바꿔가면서 코드를 제출했으니 말이죠.
https://www.acmicpc.net/problem/1753
https://www.acmicpc.net/problem/18352
https://www.acmicpc.net/problem/1446
https://www.acmicpc.net/problem/5972
https://www.acmicpc.net/problem/17396
근데, 이번에 계속 다익스트라 알고리즘을 사용하면서도 제가 잘못된 다익스트라 알고리즘을 사용하고 있다는 것을 알았습니다. 아래 링크의 내용입니다.
http://www.secmem.org/blog/2019/01/09/wrong-dijkstra/
제가 설명하기엔 너무나 좋은 내용이고 다시 글을 정리해봤자 똑같은 내용이 될 것 같아 링크로 남깁니다.
제가 위의 링크에 있는 내용, 코드를 제 입맛에 맞춘 코드는 아래 링크에 있습니다.
https://github.com/shinkeonkim/Today_PS/blob/master/algorithm/dijkstra.cpp
'내가 공부하려고 만들어가는 목록' 카테고리의 다른 글
[내공만목] 대충 어린이날에 푼 골드 문제들 정리 (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 |