Topological Sort (위상 정렬)
- Algorithm
- 2021년 4월 12일
조건 : 방향이 있고 사이클이 없는 그래프 (Directed Acyclic Graph) DAG일때, 방향성을 거스르지 않고 나열하는 것으로 순서가 있는 작업을 차례로 수행해야할때 순서를 결정해주기 위해 사용하는 알고리즘이다. 대학 커리큘럼의 선수과목이나 엄무의 일정을 시간 순서대로 배치한것이 그 예 이다. 1. 특징 방향이 있는 그래프이어야 한다. (directed) 사이클이 없어야 한다. (Acyclic) 2. Pesudo Code 1) InDegree 이용방법 2) dfs 이용방법 3. 구현 방법 1) InDegree 이용 모든 vertex에 대해 InDegree값을 초기화 진입 차수 (indegree)가 0인 값을 큐에 삽입 큐에서 1개 vertex, v를 pop v를 stack에 쌓기 (정렬한 값을 담는 것이 stack) v에 연결된 vertex들의 indegree값을 1감소 진입 차수가 0인 정점들을 큐에 삽입 3-6번을 Vertex수만큼 반복 만약에 큐가 비어있다면, 사이클이 존재하는 그래프 (큐가 비어있다면 indegree가 0인 값이 없었다는 소리. 즉, 사이클 발생) 2) dfs 이용 방문하지 않은 vertex들을 dfs함수 진행. dfs 해당 vertex 방문표시 인접 vertex에 대해 방문하지 않았다면 dfs함수 진행 dfs함수 종료시 stack에 push 4. 시간 복잡도 indegree방법은 초기화하는데 O(V), 큐에 삽입, 제거 하는게 O(V)번씩 소요되며, indegree를 1감소 시켜주는게 O(E)번 일어난다. (indegree를 1감소해주는건 edge를 삭제해주는거와 같기 때문) 따라서, O(V+E)의 시간복잡도를 갖는다....
Read MoreCounting Sort ( 계수 정렬 )
- Algorithm
- 2020년 10월 13일
계수 정렬은 삽입, 버블, 선택, 퀵, 합병 정렬들과 같이 비교를 수행하는 방식이 아닌 비교를 하지 않는 Non-Comparisions Sorting Algorithm 이다. 그러면 여기서 값을 정렬하는데 어떻게 비교 없이 수행하나요? 와 같은 질문이 있을 텐데, 계수 정렬은 비교 대신 정렬할 수의 개수와 배열의 인덱스를 가지고 정렬을 수행하게 된다. 1. 기본적인 흐름 2 1 2 4 5 3 6 5 3 을 정렬하고자 한다면 1의 개수는 1개, 2의 개수는 2개, 3의 개수는 2개, 4의 개수는 1개, 5의 개수는 2개, 6의 개수는 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^2) O(n^2) 트리 정렬 Ω(nlogn) Θ(nlogn) O(n^2) 퀵 정렬 Ω(nlogn) Θ(nlogn) O(n^2) 셸 정렬 Ω(n) Θ(n^1.5) O(n^1.5) 힙 정렬 Ω(nlogn) Θ(nlogn) O(nlogn) 합병 정렬 Ω(nlogn) Θ(nlogn) O(nlogn) 큐브 정렬 Ω(n) Θ(nlogn) O(nlogn) 팀 정렬 Ω(n) Θ(nlogn) O(nlogn) 기수 정렬 Ω(nk) Θ(nk) O(nk) 계수 정렬 Ω(n+k) Θ(n+k) O(n+k) 3. 공간 복잡도 ( Big-O ) 알고리즘 최악 선택 정렬 O(1) 버블 정렬 O(1) 삽입 정렬 O(1) 셸 정렬 O(1) 힙 정렬 O(1) 퀵 정렬 O(logn) 합병 정렬 O(n) 큐브 정렬 O(n) 트리 정렬 O(n) 팀 정렬 O(n) 계수 정렬 O(k) 기수 정렬 O(n+k) 4. 정렬의 특성 1) 안정 정렬( stable sort ) 정렬되지 않은 상태의 같은 키값을 가진 원소의 순서가 정렬 후에도 유지 되는 정렬 상황에 따라서 객체나 키값이 여러개인 값들을 정렬 하려고 할때 원래의 순서가 바뀌게 되면 안될 수 있기 때문에 그때는 stable한 sort를 이용해야 한다. Bubble, Insertion, Merge, Counting, Bucket, Radix Sort가 해당된다. Note...
Read More