Topological Sort (위상 정렬)
- Algorithm
- 2021년 4월 12일
조건 : 방향이 있고 사이클이 없는 그래프 (Directed Acyclic Graph) DAG일때, 방향성을 거스르지 않고 나열하는 것으로 순서가 있는 작업을 차례로 수행해야할때 순서를 결정해주기 위해 사용하는 알고리즘이다. 대학 커리큘럼의 선수과목이나 엄무의 일정을 시간 순서대로 배치한것이 그 예 이다. 1. 특징 방향이 있는 그래프이어야 한다. (directed) 사이클이 없어야 한다. (Acyclic) 2. Pesudo Code 1) InDegree...
Read MoreCounting Sort ( 계수 정렬 )
- Algorithm
- 2020년 10월 13일
계수 정렬은 삽입, 버블, 선택, 퀵, 합병 정렬들과 같이 비교를 수행하는 방식이 아닌 비교를 하지 않는 Non-Comparisions Sorting Algorithm 이다. 그러면 여기서 값을 정렬하는데 어떻게 비교 없이 수행하나요? 와 같은 질문이 있을 텐데, 계수 정렬은 비교 대신 정렬할 수의 개수와 배열의 인덱스를 가지고 정렬을 수행하게 된다. 1. 기본적인 흐름 2 1 2 4 5 3 6 5 3 을 정렬하고자 한다면 1의...
Read MoreSorting Algorithm
- Algorithm
- 2020년 9월 20일
1. 종류 선택 정렬 ( Selection Sort ) 삽입 정렬 ( Insertion Sort ) 버블 정렬 ( Bubble Sort ) 셸 정렬 ( Shell Sort ) 퀵 정렬 ( Quick Sort ) 힙 정렬 ( Heap Sort ) 합병 정렬 ( Merge Sort ) 기수 정렬 ( Radix Sort ) 계수(카운트) 정렬 ( Count Sort ) 트리 정렬 큐브 정렬 팀 정렬 2. 시간 복잡도 ( Big-O ) 알고리즘 최선 평균 최악 선택 정렬 Ω(n^2) Θ(n^2) O(n^2) 버블 정렬 Ω(n) Θ(n^2) O(n^2) 삽입 정렬 Ω(n) Θ(n...
Read More