Dijkstra visited 사용 기준
다익스트라에서 visited가 꼭 필요한지, 우선순위 큐 구현에서 outdated entry를 어떻게 처리하는지 정리합니다. dist 배열, heap 중복 삽입, 음수 간선 불가 조건, 구현 실수까지 예제로 설명합니다.
-
-
0-1 BFS는 다익스트라와 무엇이 다를까: 가중치가 0과 1일 때 deque를 쓰는 이유
0-1 BFS가 다익스트라와 어떻게 다르고, 간선 가중치가 0과 1일 때 deque로 최단거리를 구할 수 있는 이유를 설명합니다.
-
다익스트라에서 우선순위 큐에 같은 노드가 여러 번 들어가도 되는 이유
다익스트라에서 우선순위 큐에 같은 노드가 여러 번 들어가는 이유를 stale entry, dist 배열, continue 조건으로 설명합니다.
-
플로이드 워셜 알고리즘 정리: 다익스트라와 무엇이 다를까
플로이드 워셜을 쉽게 설명합니다. 모든 정점 쌍 최단거리 문제에서 왜 다익스트라와 다르게 생각해야 하는지 코딩테스트 기준으로 정리합니다.
-
다익스트라 알고리즘 입문: 가중치가 있는 최단거리는 왜 BFS가 안 될까
다익스트라 알고리즘을 쉽게 설명합니다. BFS가 되는 최단거리와 안 되는 최단거리 차이, 우선순위 큐가 왜 필요한지 코딩테스트 기준으로 정리합니다.
-
BFS 문제 풀이 패턴 정리: 최단거리 문제에서 BFS를 바로 떠올리는 방법
BFS 문제 풀이 패턴을 정리합니다. 최단거리, 레벨 탐색, 상태 전이 문제에서 어떤 신호가 보이면 BFS를 떠올려야 하는지 코딩테스트 기준으로 설명합니다.
