프로그래밍 언어들/알고리즘 썸네일형 리스트형 그래프의 행렬 표현법(Representations of graphs) 그래프의 행렬 표현법(Representations of graphs) 1. 방향성이 없는 그래프와 방향성이 있는 그래프 (1) 방향성이 없는 그래프 [ 출저 : Introduction to algorithms 3/E ] 위의 그림을 보면 (a)의 그래프는 5개의 꼭지점과 7개의 선을 가지고 있다. (a)의 그래프를 인접 리스트로 표현해놓은 것이 (b)의 그림이다. 꼭지점 1의 경우 2와 5에 인접해 있고, 꼭지점 2의 경우 모든 다른 꼭지점과 인접해 있다. 이것을 행렬로 표현하면 (c)와 같다. 행은 현재 꼭지점이 되는 것이고, 열은 다른 꼭지점이라고 생각하면 된다. 즉 위의 그림과 무관하게 아래 행렬을 살펴보자. 1 2 3 4 5 1 0 0 1 0 0 2 0 0 1 1 0 3 1 1 0 0 0 4 0 .. 더보기 병합 정렬(Merge Sort) 병합 정렬(Merge-Sort) - 배열의 원소를 완전 분해한 후에 다시 병합하며 정렬하는 방식 - 항상 O(n log n)의 복잡도를 가진다 1. 동작 원리 (1) 주어진 배열을 2개의 파티션으로 나눈다. (2) 하나의 원소가 남을 때까지 (1)의 과정을 재귀적으로 반복한다. (3) 완전 분해한 원소를 다시 병합하며 정렬을 수행한다. 2. 함수 설명 - merge_sort() : 동작원리 (1)과 (2)에 해당하는 기능을 수행한다. - merge() : 동작원리 (3)에 해당하는 기능을 수행한다. #include #include #include #include #define MAX 10 // size of array #define INF 10000 // infinity value void display.. 더보기 힙 정렬(Heap Sort) 힙 정렬(Heap-Sort) - 최대 힙 트리 또는 최소 힙 트리를 구성해 정렬하는 방식 - 일반적으로 O( n log n)의 복잡도를 가진다. ( 퀵 정렬은 최악의 경우 O(n²)의 복잡도를 가지기 때문에 힙 정렬이 선호된다.) 동작 원리 1. 최대(최소) 힙을 구성한다. 자노드를 가진 부노드부터 구성하며, 아래부터 루트까지 순차적으로 구성한다. 2. 루트에 위치한 수와 가장 작은 수를 교환한다. 3. 교환한 수를 제외하고 힙의 특성을 유지시킨다. 4. 위의 2와 3 과정을 반복한다. 함수 설명 - heap_sort() : 동작 원리 "2"의 과정을 수행하는 함수 - build_max_heap() : 동작 원리 "1"의 과정을 수행하는 함수로 기본적인 힙의 구조를 구성한다. - max_heapify().. 더보기 퀵 정렬(Quick Sort) 1. 퀵 정렬(Quick-Sort) - 퀵 정렬의 내부 루프는 대부분 컴퓨터의 아키텍처에서 효율적으로 작동하도록 설계되어 있다. ( 메모리 참조가 지역화되어 있기 때문에 CPU 캐시의 히트율이 높기 때문 ) - 일반적으로 퀵 정렬은 평균적으로 O(n log n)번의 비교를 수행한다. ( 최악의 경우 O(n²) ) - 정렬을 위해 작은 공간( O(log n) )의 메모리를 필요로 한다. 2. 동작 원리 1. 리스트의 중간 원소를 피벗으로 지정한다. 2. 피벗을 기준으로, 앞에는 피벗보다 값이 작은 원소들을 배치하고 뒤에는 피벗보다 값이 큰 원소들을 배치한다. ( 이렇게 리스트를 나누는 것을 "분할(partition)"이라고 한다. ) 3. 분할된 두 개의 리스트에 대해 재귀적으로 이 과정을 반복한다. #i.. 더보기 선택 정렬(Selection Sort) 선택 정렬(Selection-Sort) - 남은 배열의 원소들 중 최소 값을 찾아 현재 포지션(맨 앞)에 위치 시키는 방식 - O(n2)의 복잡도를 가진다. #include #include #include #define MAX 10 // size of array void display_elements( int *, int); void selection_sort( int *, int); int main( void) { int arry[MAX] = { 0,}; int count = 0; int size = 0; srand( time(NULL)); // used to init random size = sizeof(arry)/4; // init elements of array with random numbers.. 더보기 삽입 정렬(Insertion-Sort) 삽입 정렬(Insertion Sort) - 배열의 모든 원소를 앞에서 부터 차례대로 비교하여, 자신의 위치를 찾아 삽입하는 방식 - 작은 원소의 정렬에 효율적인 알고리즘 - *In-place 알고리즘의 한 종류 * 원소를 저장하고 있는 초기 배열의 아주 작은 추가적인 공간만 요구하는 알고리즘 * "아주 작은"이란 n 개의 원소를 정렬할 때, O(log n) 만큼의 추가 공간이 요구되는 것 #include #include #include #define MAX 10 // size of array void display_elements( int *, int); void insertion_sort( int *, int); int main( void) { int arry[MAX] = { 0,}; int count.. 더보기 이전 1 2 3 다음
