Dev_Diary

https://www.acmicpc.net/problem/1854다익스트라 알고리즘 문제입니다. 사실 다익스트라 알고리즘보다는 우선순위 큐 문제라고 할 수 있을 것 같습니다.다익스트라의 핵심 아이디어인 '다음 노드까지 도달 시간이 현재 최단시간보다 길면 큐에 삽입하지 않는다' 를 제외하기 때문입니다. 이는 당연히 k 번째 최단 시간을 구하기 위해서는 적어도 K 번은 같은 노드를 반복해서 방문해야 하기 때문입니다.그렇게만 진행하면 우리는 크게 두 가지 해결해야 하는 과제가 생깁니다. 1. 만약 순환이 생긴다면 모든 노드를 큐에 집어넣었을 때 종료 조건이 존재하지 않습니다.좋은 예시가 바로 예제입니다.우리는 탐색을 진행하며 2 - 3 - 5 의 순환이 무한히 반복될 수 있음을 알 수 있습니다. 그렇다면 모든..

https://www.acmicpc.net/problem/7662우선순위 큐를 두 개 사용해서 풀 수 있는 문제입니다.최대힙, 최소힙 두 개를 사용해 풀 수 있는데, 문제는 이 두 힙을 동기화 시키는 것 입니다. 가장 작은 수를 최소힙을 통해 제거했다고 가정하겠습니다. 최대힙에서는 이 수를 제거한 사실이 자동으로 업데이트 되지 않습니다. 그렇다고 최대힙에서 해당 수를 찾아 제거하는 방식은 우선순위 큐를 사용하는 이점을 살릴 수 없습니다. 그렇기에 우리는 다른 방식을 찾아야 합니다. 일반적인 방법으로 쿼리의 순서를 기억해 삭제했는지 체크하는 방법이 있습니다.그래프를 탐색할 때 탐색여부를 체크하기 위해 visited 를 만드는 것 처럼 삭제한 쿼리를 기억해 최대힙 / 최소힙 에서 해당 데이터를 삭제 시 이미..

https://www.acmicpc.net/problem/1715먼저 합친 카드패를 연속해서 더하게 되는 방식이므로 작은 패부터 더해주는 것이 최적의 수가 되는 전형적인 그리디 알고리즘 문제입니다.다만 여러 패들 중에 더한 패를 들고 계속 더하는 것이 아닌 더한 패를 다시 패들 속에 섞고 그들 중 가장 작은 패 두개를 더하는 방식으로 여러 번 진행해야 합니다.즉 추가하고 뽑고를 반복해야 하니 효율적인 진행을 위해 우선순위큐를 사용하는 것이 합리적입니다.import sysimport heapqinput = sys.stdin.readlinedef solution(N, bundles): # 번들 리스트 힙으로 치환 heapq.heapify(bundles) # 카운트 cnt = 0 #..