언제나 휴일

[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

[C언어 알고리즘] 3.2.1 하노이 타워 알고리즘 성능 분석 하노이 타워 알고리즘 성능을 분석합시다. n 개 돌을 옮기는 데 걸리는 수행 시간을 T(n)이라고 합시다. 하노이 타워 알고리즘의 수행 시간 T(n)은 T(n-1) 2번과 Move 1번으로 진행합니다. T(n) = 2*T(n-1) + 1 = 2 *T(n-2) + 2 +1 = 2^2*T(n-3) +4+2+1 = ... = 2^n -1 따라서 하노이 타워 알고리즘 수행 시간은 O(2^n)이라고 말할 수 있습니다. [그림 3.2] 하노이 타워 알고리즘

[C언어 알고리즘] 3.2 하노이 타워 재귀 알고리즘 중에 하노이 타워가 있습니다. 하노이 타워 알고리즘은 n 개의 돌을 이동시키는 문제입니다. 세 개의 기둥이 있고 하나의 기둥에 n 개의 돌이 크기 순으로 있습니다. 한 번에 하나의 돌을 이동할 수 있고 작은 돌 위에 큰 돌이 올 수 없습니다. 이와 같은 규칙을 이용하여 n 개의 돌이 있는 기둥에서 다른 기둥으로 모든 돌을 옮기는 문제입니다. [그림 3.1] 하노이 타워 이 문제를 재귀적으로 해결하면 다음과 같은 방법으로 해결할 수 있습니다. 가정: n-1개의 돌을 옮길 수 있다. 가정에 의해 먼저 A에 있는 n-1개의 돌을 C를 이용하여 B로 옮깁니다. 규칙에 의해 1개의 돌을 A에서 C로 옮깁니다. 가정에 의해 B에 있는 n-1개의 돌을 A를 이용하..