프밍노트

K번째 최단경로를 찾는 문제 사용했던 경로를 제거했던 거의 최단경로 와 비슷하다고 생각했지만. 해당 문제는 사용했던 경로 까지 생각해서 K째 경로를 찾는 문제다. 문제 풀이방법은 BFS 로 우선순위는 거리가 적게 이동한 순서로 우선순위 큐를 만들어준다. 만약 아직 이동 cost가 K 번째가 아니라면 BFS로 이동을 해준다. 최우선 거리를 먼저 실행하기에 도착했을때 몇번째로 도착했는지만 알수있다면 끝난다. 그렇게 모든노드를 K번째 방문했을때 BFS를 끝내주면 된다. #include#include#include#includeusing namespace std;void K_MST() { unordered_map> KMap; unordered_map> K_reverse_Map; // 0 = 최단거리..

데바데 자동 구매는 어떤 방법일까? 해서 심심해서 비슷하게 구현해보았다. 데드바이 데이라이트를 플레이하던 중 게임에는 아래와 같이아이템을 구매하는 시스템이 존재한다. 해당 페이지의 중앙 버튼은 아이템을 자동으로 구입해 주는 시스템인데 아무 생각 없이 보고 있다 문득 해당 페이지에서 사용하는 알고리즘이 무엇인지 궁금해졌다 처음 문득 생각했을 때는 다익스트라 또는 최소 스패닝트리를 사용했을 거 같았다. 당연하게도 전체적으로 가장 저렴한 루트를 제공할 것이라고 생각했기 때문이다. 알고리즘을 분석하기위해 자동 구매를 하며 영상녹화 한 뒤 분석하던 도중 이상한 순서로 구매하는 것을 확인하고 의문이 들어서 찾던 중 아래와 같은 사실을 확인해 버렸다. 깊이가 가까운 노드에서 가격이 저렴한 순서대로 샀다는 것..