naverstop   11달 전

 Node js로 minheap을 구현하여 문제를 풀었는데 정답처리를 받았습니다.

그런데 min heap 에 1 2 3 순서대로 add(추가)를 진행하고 3번 heappop(제거)를 진행하니 1 2 3 순서가 아니라 1 3 2 순서로 출력이 되는것을 확인했습니다.

그래서 1927번 문제 '최소 힙' 에 minheap 부분만 떼어내서 제출해본 결과 오답이 나왔습니다.


제가 다익스트라 알고리즘을 잘 모르는건가요?

알려주시면 감사하겠습니다!

seungwuk98   11달 전

다익스트라에서 heap을 사용하는 이유는 업데이트의 개수를 최소화하기 위해서입니다. 

1->2 해야되는것을 1->3했다가 1->2로 한다고 해서 정답이 틀린건 아닙니다. 성능이 조금 떨어질 뿐이죠.

댓글을 작성하려면 로그인해야 합니다.