최소 스패닝 트리는 왜 간선을 정렬할까: 크루스칼과 유니온 파인드가 만나는 지점
최소 스패닝 트리에서 크루스칼 알고리즘이 간선을 정렬하는 이유와 유니온 파인드가 사이클을 막는 과정을 예제로 설명합니다.
-
-
Dijkstra visited 사용 기준
다익스트라에서 visited가 꼭 필요한지, 우선순위 큐 구현에서 outdated entry를 어떻게 처리하는지 정리합니다. dist 배열, heap 중복 삽입, 음수 간선 불가 조건, 구현 실수까지 예제로 설명합니다.
-
SCC 쉽게 이해하기
SCC를 쉽게 설명합니다. 방향 그래프에서 서로 왕복 가능한 정점 덩어리를 왜 묶는지, condensation graph가 왜 DAG가 되는지, Kosaraju와 Tarjan 감각까지 단계적으로 정리합니다.
-
오일러 경로 vs 해밀턴 경로 쉽게 이해하기
오일러 경로와 해밀턴 경로 차이를 쉽게 설명합니다. 간선 기준과 정점 기준이 어떻게 다른지, 존재 조건과 난이도 차이가 왜 크게 갈리는지 코딩테스트 예시 중심으로 차분하게 정리합니다.
-
DAG DP 쉽게 이해하기
DAG DP를 쉽게 설명합니다. 위상 정렬 뒤에 DP가 붙는 순간 왜 막히는지, 상태 정의를 어떻게 잡아야 하는지, 값 전파와 최장 경로 예시를 코딩테스트 기준으로 단계적으로 정리합니다.
-
플로이드 워셜 알고리즘 정리: 다익스트라와 무엇이 다를까
플로이드 워셜을 쉽게 설명합니다. 모든 정점 쌍 최단거리 문제에서 왜 다익스트라와 다르게 생각해야 하는지 코딩테스트 기준으로 정리합니다.
