위상정렬 (Topological sort) 는 cycle이 없는 방향 그래프(Directed Acyclic Graph,DAG) 에서 정점들을 선형순서(간선의 방향을 거스리지 않도록)로 나열하는 것을 의미하며, 주어진 그래프내에서 여러 개의 위상 정렬 결과가 나올수도 있다.
대표적으로 위상정렬을 이용하는 예로 대학교 선수과목 수강 순서를 정할떄 이용할 수 있다.
위상 정렬 알고리즘의 수행과정은 다음과 같다.
B Tree는 다수의 키를 가진 Node로 구성되어 다방향 탐색이 가능한 균형 트리이다.
B Tree는 이진트리와 다르게, 하나의 노드에 다수개의 키를 저장할 수 있어, Tree의 높이를 낮추어 대용량 데이터 처리에 효율적임으로, 관계형 데이터베이스의 기본 자료구조로서 활용된다.
( 균형 트리란 ? 왼쪽,오른쪽 subtree의 높이 차이를 줄여, O(logN)의 시간복잡도를 가지고, 탐색,삼입,삭제 연산을 수행할수 있다. )
대표적으로 AVL Tree, RB Tree, B tree…등이 있다.
차수가 M인 B트리는 다음과 같은 정의를 갖는다.
(= 트리 노드의 최대 자식 노드의 개수가 M이며, 이떄 M은 2이상의 정수여야한다.)
Quick sort는 기준 데이터인 pivot 을 설정하고, pivot보다 작은 값과 pivot보다 큰 값의 위치를 교환하고, 두 개의 포인터가 어긋나는 시점에 왼쪽에 위치한 포인터를 pivot과 교환해줌으로서, pivot의 왼쪽에는 pivot보다 작은 값들만 , pivot의 오른쪽에는 pivot보다 큰 값들만 위치하도록 한다.
pivot의 왼쪽, 오른쪽 부분의 배열에 대해서 다시 재귀적으로 정렬을 수행하는 정렬 알고리즘이다.
플루이드의 토끼와 거북이 알고리즘은 Linked List에서 cycle 존재 유무와 cycle의 길이 및 , 시작점 을 확인할 수 있는 알고리즘으로 2개의 다른 속도로 움직이는 포인터를 사용한다. , (알고리즘 이름이 왜 토끼와 거북이인지 알 것 같다)
알고리즘은 크게 2 phase로 나뉜다.
Phase 1. 다른 속도로 움직이는 두 pointer의 교차점을 찾고,
Phase 2. cycle의 진입로를 찾는다.
먼저 phase 1을 세부적으로 살펴보면,
merge sort(합병정렬) 은 크기가 N인 입력을 1/n 크기로 분할하고, 각각에 대해 재귀적으로 다시 합병정렬을 수행한 후,n개의 정렬된 부분은 합병하는 정렬 알고리즘이다.