언제나 휴일

[C언어 알고리즘] 3.4.3 이진 탐색 트리 구현 이제 이진 탐색 트리를 구현합시다. 이진 탐색 트리는 자료를 보관하는 컬렉션 중에 탐색 효율성을 높인 자료구조입니다. 여기에서는 도서를 보관하는 이진 탐색 트리를 구현하기로 할게요. 먼저 노드를 정의합시다. 이진 탐색 트리의 노드는 데이터와 왼쪽 자식 노드의 위치, 오른쪽 자식 노드의 위치로 구성합니다. 이 책에서는 삭제 편의성을 위해 부모 노드의 위치도 포함할게요. 그리고 동적으로 노드를 생성하는 함수를 제공합시다. typedef struct _Node Node; struct _Node { Book *book; Node *lch; Node *rch; Node *pa; }; Node *New_Node(Book *data); 이진 탐색 트리에는 root ..

[C언어 알고리즘] 3.4.2 이진 탐색 트리(Binary Search Tree)이번에는 재귀 알고리즘으로 구현하는 이진 탐색 트리(Binary Search Tree)를 알아봅시다. 이진 탐색 트리는 검색 효율을 높이기 위해 만들어진 이진 트리입니다. 이진 탐색 트리에서는 자료를 보관할 때 부모보다 작은 값을 갖는 자료는 부모의 왼쪽 서브 트리에 매달고 큰 값을 갖는 자료는 부모의 오른쪽 서브 트리에 매다는 이진 트리입니다. 그리고 이진 탐색 트리에서는 같은 값을 갖는 자료는 보관하지 않습니다. 이처럼 매달면 서브 트리도 이진 탐색 트리인 특징을 갖습니다. binary search tree = { root, sub trees} sub tree is binary search tree, left son’ s..

[C언어 알고리즘] 3.4.1 트리의 용어[그림 3.7] 트리의 구조 트리에는 부모가 없는 노드가 없거나 유일합니다. 그리고 이를 루트라고 말합니다. 그리고 트리에서 자료를 보관하는 것을 정점(Vertex) 혹은 노드(Node)라고 부르며 정점에서 다른 정점으로 가는 경로를 간선(Edge) 혹은 링크(Link, 다른 노드의 위치 정보)라고 부릅니다. 언제나 트리의 정점은 간선 개수보다 1개 많습니다. N(V) = N(E)+1 , N(V)는 정점의 개수, N(E)는 간선의 개수 루트에서 자신에게 걸리는 거리를 레벨(Level)이라 부르고 루트를 Level 1로 출발합니다. 그리고 가장 높은 레벨(Level)을 트리의 높이(Height) 혹은 깊이(Depth)라고 부릅니다. 간선은 링크 혹은 가지라고도 부르..

[C언어 알고리즘] 3.4 이진 탐색 트리 이번에는 재귀 알고리즘으로 구현하는 이진 탐색 트리를 알아봅시다. 이진 탐색 트리는 검색 효율을 높이기 위해 만들어진 트리입니다. 이진 탐색 트리를 살펴보기 전에 먼저 트리가 무엇인지 살펴보기로 해요. 트리는 대표적인 비선형 자료구조입니다. 비선형 자료구조는 자료를 보관하는 구조를 하나의 선의 형태로 표시할 수 없는 자료구조를 말하며 트리와 그래프 등이 있습니다. 그 중에 트리는 뿌리에서부터 계층적으로 자료를 보관하는 자료구조입니다. 트리는 방향성 있는 그래프로 표현하며 사이클이 존재하지 않고(ACycle) 고립 상태가 없는(No Island) 자료구조입니다. 트리는 다음처럼 루트와 서브 트리의 집합으로 정의할 수 있습니다. Tree = {root , sub t..

[C언어 알고리즘] 3.3.3 퀵 정렬 알고리즘 소스 코드//퀵 정렬(Quick Sort) #include #define SWAP(a,b) {int t; t = a; a=b; b=t;}//a와 b를 교환 int *origin; int on; void QuickSort(int *base, int n); void ViewArr(int *arr, int n); int main(void) { int arr[10] = { 9,4,3,10,5,8,7,6,2,1 }; origin = arr; on = 10; ViewArr(arr, 10); QuickSort(arr, 10); ViewArr(arr, 10); return 0; } void PrintSpace(int n); void QuickSort(int *base, ..

[C언어 알고리즘] 3.3.2 퀵 정렬 알고리즘 구현퀵 정렬 알고리즘을 구현합시다. 퀵 정렬(base:컬렉션,n: 원소 개수, compare:비교 논리) 조건(n

[C언어 알고리즘] 3.3.1 퀵 정렬 알고리즘 성능 분석 퀵 정렬 알고리즘 성능을 분석합시다. 퀵 정렬(base:컬렉션,n: 원소 개수, compare:비교 논리) 조건(n

[C언어 알고리즘] 3.3 퀵 정렬(Quick Sort) 알고리즘 퀵 정렬 알고리즘은 재귀적인 방법으로 문제를 해결하는 알고리즘입니다. 퀵 정렬 알고리즘은 피벗 값을 선택하여 피벗 값보다 작은 값들은 왼쪽으로 보내고 큰 값들은 오른쪽으로 보낸 후에 이들 사이에 피벗을 위치시키는 원리를 이용합니다. 이후 피벗보다 작은 값들을 재귀 호출로 정렬하고 피벗보다 큰 값들도 재귀 호출로 정렬하는 방식입니다. 그런데 퀵 정렬은 어떠한 요소를 피벗으로 선택하냐에 따라 성능에 차이가 납니다. 만약 전체 요소의 중간 순위의 요소를 선택하면 재귀 호출에서 반씩 나누어 정렬을 하게 되어 좋은 성능을 발휘합니다. 하지만 가장 작은 값이나 가장 큰 값을 피벗으로 선택하면 최악의 성능을 발휘합니다. 여기에서는 맨 앞과 맨 뒤, 그..

[C언어 알고리즘] 3.2.3 하노이 타워 알고리즘 소스 코드//Program.c #include #include void Hanoi(const char *src, const char *use, const char *dest, int n) { if(n

[C언어 알고리즘] 3.2.2 하노이 타워 알고리즘 구현 하노이 타워 알고리즘을 구현합시다. 알고리즘은 입력 인자로 세 개의 기둥과 돌의 개수를 받아야 합니다. void Hanoi(const char *src, const char *use, const char *dest, int n) { 만약 돌이 없으면 아무 것도 수행하지 않고 함수를 종료합니다. 즉 탈출 조건입니다. if(n