Dijkstra, Heap, Red-Black Tree
Dijkstra's Shortest-Path Algorithm BFS 는 undirected graph 에서 최단 경로를 찾지만, 이건 모든 edge 의 길이가 1일때만 그렇다. 다익스트라(dijkstra, 데이크스트라) 알고리즘은 directed graph 에서 non-negative length 에 대한...
Heap
C++ 힙 정렬 (Heap Sort), Bottom-up 과 Top-down 구현
Heap sort 힙 소트 는 선택 정렬군중 하나로서, 비교 기반 정렬 알고리즘입니다. 선형 시간(Linear Time) 탐색을 이용하는 기본적인 Selection Sort 보다 로그 시간(Logarithmic Time) 복잡도를 가지는 우선순위 큐를...
C++ 정렬 알고리즘, Merge, Quick, Selection, Insert, Bubble, Heap
Stability 우선 A에 대해 정렬을 하고, 그 정렬된 결과를 바탕으로 B에 대해 정렬했을때 정렬 순서가 그대로 유지되는 알고리즘을 stable 하다고 합니다. merge 가 대표적인 stable 정렬, quick 이...