언제나 휴일

7.3 이진 탐색 트리 설계 및 사용 이번에는 이진 탐색 트리 설계 및 이를 사용하는 프로그램을 작성합시다. 여기에서 구현할 이진 탐색 트리는 도서 개체를 보관하고 삭제, 검색, 전체 보기를 할 수 있는 기능을 제공하기로 해요. STL에서 제공하는 map 사용하는 방법을 익히고 난 후에 다시 한 번 STL의 map을 모델로 자신의 map을 구현할 것입니다. 여기에서는 이진 탐색 트리 개념을 잡기 위해 비교적 간단하게 구현해 보아요. 프로젝트를 생성한 후에 공통으로 사용할 파일(3.1.1 참고)을 추가하세요. 그리고 여기에서 보관할 도서를 Book 클래스로 정의합시다.class Book{도서는 상수화 멤버로 도서 번호와 도서명을 멤버 필드로 추가하세요. const int bnum; string title;..

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

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

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

6.3 이진 탐색(Binary Search)이진 탐색(Binary Search) 알고리즘은 정렬 상태의 배열에서 원하는 자료를 탐색하는 알고리즘으로 재귀적인 방법으로 구현할 수 있는 대표적인 알고리즘입니다. 배열의 중간에 있는 요소와 검색 자료를 비교하여 크면 뒤쪽 배열에서 재귀적으로 탐색하고 작으면 앞쪽 배열에서 재귀적으로 탐색합니다. 만약 같은 자료를 찾거나 배열의 원소 개수가 0이면 탐색을 끝냅니다. 위치 BinarySearch(base: 배열, n: 원소 개수, value: 검색할 값) 조건 n0) 반환 BinarySearch(base,n/2, fun) 반환 BinarySearch(base+n/2+1,n - n/2, fun) 순차 탐색한다면 최악의 경우 모든 요소와 비교해야 하므로 O(n) 성능을..

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

6.1 하노이 타워 하노이 타워는 대표적인 재귀 알고리즘입니다. 하노이 타워 알고리즘은 n 개의 돌을 이동시키는 문제입니다. 세 개의 기둥이 있고 하나의 기둥에 n 개의 돌이 크기 순으로 있습니다. 한 번에 하나의 돌을 이동할 수 있고 작은 돌 위에 큰 돌이 올 수 없습니다. 이와 같은 규칙을 이용하여 n 개의 돌이 있는 기둥에서 다른 기둥으로 모든 돌을 옮기는 문제입니다. 이 문제를 재귀적으로 해결하면 다음처럼 해결할 수 있습니다. 가정: n-1개의 돌을 옮길 수 있다. 가정에 의해 먼저 A에 있는 n-1개의 돌을 C를 이용하여 B로 옮깁니다. 규칙에 의해 1개의 돌을 A에서 C로 옮깁니다. 가정에 의해 B에 있는 n-1개의 돌을 A를 이용하여 C로 옮깁니다. 따라서 n개의 돌을 옮길 수 있습니다. 의..

6. 재귀 알고리즘 이번에는 재귀 알고리즘을 살펴봅시다. 재귀 알고리즘은 문제를 해결하기 위해 자신의 알고리즘을 이용해서 해결하는 알고리즘입니다. 수학에서 명제가 참인지 거짓인지 증명하기 위해 명제를 이용해서 증명하는 방법과 같은 방식입니다. 예를 들어 "n! 을 f(n)이라고 할 때 f(1)=1이고 n>1인 정수이면 f(n)=n*f(n-1)이다."라는 명제를 증명하면 다음처럼 증명할 수 있습니다. n-1일 때 위 명제가 참이라고 가정합시다. 가정에 의해 f(n-1) = (n-1)*(n-2)*(n-3)*...*3*2*1입니다. f(n) = n*(n-1)*(n-2)*(n-3)*...*3*2*1 = n*f(n-1) 이므로 위 명제는 참인 명제입니다. 이처럼 명제 자신을 이용하여 명제를 증명하는 것을 재귀적 ..

5. list 만들기 이번에는 STL의 list를 모델 삼아 list를 만들어 보기로 해요. 4장에서는 vector를 만들었습니다. 그 프로젝트에서 헤더파일 포함문과 using 문만 변경하세요. //#include //#include //using std::vector; //using std::find; //using std::find_if; #include "list.h" #include "algorithm.h" using ehlib::list; typedef list Genres; typedef Genres::iterator GIter; typedef Genres::const_iterator GCIter; 물론 list.h 파일과 algorithm.h 파일을 프로젝트에 추가하세요. alogorithm..

4. vector 만들기 이번에는 STL의 vector를 모델 삼아 vector를 만들어 보기로 해요. 3장에서는 vector를 사용했습니다. 그 프로젝트에서 헤더파일 포함문과 using 문만 변경하세요. //#include //#include //using std::vector; //using std::find; //using std::find_if; #include "vector.h" #include "algorithm.h" using ehlib::vector; typedef vector Genres; typedef Genres::iterator GIter; typedef Genres::const_iterator GCIter; 물론 vector.h 파일와 algorithm.h 파일을 프로젝트에 추가하..