Information of IT

Topological Sort (위상 정렬)Topological sort는 Direct Acyclic Graph의 경우에서 문제를 해결하는 방법이다. 방향이 존재하는 그래프에서 각 vertex의 선행 순서 정보를 유지하면서 모든 vertex를 탐색하는 알고리즘이다. Type of Edges 알고리즘을 알아보기 전에, Direct Acyclic Graph를 알기 위해 방향이 있는 그래프에서 DFS를 실행할 때 나타나는 edge의 종류를 먼저 정리해 보자.  Tree Edge: 새로운 정점을 만났을 때 생기는 edge. Edge는 한 정점에서 다른 정점을 이을 때 발생하게 된다. Tree Edge는 어떤 정점이 새로운 정점과 연결될 때 생기는 edge를 말한다.Back Edge: Back Edge는 트리에서..

최소신장트리 알고리즘 - 개 념최소신장트리 (Minimum Spanning Tree) 알고리즘 (프림 알고리즘, 크루스칼 알고리즘) 모든 정점을 포함하고 정점 간 서로 연결하면서 사이클이 존재하지 않는 그래프 I. 신장트리 (Spanning Tree)의 개요 가. 신장 트리의 정의- 모든 정점을 포함하고 정점 간 서로 연결하면서 사이클이 존재하지 않는 그래프 나. 최소신장트리의 정의- 정점 간 가중치(cost)의 합이 최소인 신장 트리  Ⅱ. 최소신장트리 알고리즘  가. Prim의 알고리즘 * 시작점 기반 최소 가중치* 정점마다 edge 검사* 우선순위 큐 기반 구현임의의 vertex를 선택, 신장 트리의 루트 노드로 삽입선택된 vertex와 인접 vertex들 사이의 edge 가중치 검사최소 가중치를 ..

개 념레코드를 비교하지 않고 준비된 버킷을 이용하여 정렬하는 방법  I. 기수 정렬 (Radix Sort)의 개요  가. 기수 정렬의 정의- 레코드를 비교하지 않고 준비된 버킷을 이용하여 정렬하는 방법 나. 기수 정렬의 특징 - O (n log2 n) 이라는 이론적인 하한선을 깰 수 있는 유일한 방법- 시간 복잡도 : O(kn) k : 버킷 수- 정렬 레코드 타입 제한  Ⅱ. 기수 정렬의 개념 및 사례  가. 기수 정렬의 개념   나. 기수 정렬 사례 (Sorting a sequence of 4-bit integers)    코드 구현 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647 public vo..

개념Pivot을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽에 위치시키는 분할과 정복에 기반한 알고리즘 I. 퀵 정렬 (Quick Sort)의 개요  가. 퀵 정렬의 정의- Pivot을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽에 위치시키는 분할과 정복에 기반한 알고리즘  나. 퀵 정렬의 특징 - 분할과 정복 기반- 재귀호출 구조- 정렬을 위한 별도의 스택이 필요- 수행시간 복잡도: O(n·log2n)  Ⅱ. 퀵 정렬의 단계 및 사례 가. 퀵 정렬의 단계 - 정렬할 원소들의 집합에서 Pivot 값을 설정- Pivot보다 큰 값은 오른쪽, 작은 값은 왼쪽- 분할된 집합의 크기가 1이 될 때까지 반복  나. 퀵 정렬의 사례 void quicksort(element list[], int left, int rig..

개 념여러 개의 자료 중에서 서로 이웃하는 키 값을 두 개씩 비교하여 순서를 결정하는 정렬 방법  I. 버블 정렬 (Bubble Sort)의 개요 가. 버블 정렬의 정의- 여러 개의 자료 중에서 서로 이웃하는 키 값을 두 개씩 비교하여 순서를 결정하는 정렬 방법  나. 버블 정렬의 특징- 간단하지만 느린 속도의 알고리즘- flag를 통해 속도 개선 가능- 수행시간 복잡도: O(n2)  Ⅱ. 버블 정렬의 단계 및 사례 가. 버블 정렬의 단계 - 인접한 두 개의 키 값을 비교함.- 앞의 키 값이 뒤의 키 값보다 크면 교환- 더 이상 비교할 대상이 없을 때까지 처음부터 반복   나. 버블 정렬의 사례 /* list에 대한 기본 버블정렬 알고리즘 */void bubble_sort(element list[], i..