언제나 휴일

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 파일을 프로젝트에 추가하..

3.5 큐를 이용한 스케쥴러 시뮬레이션 이번에는 큐를 이용하는 스케쥴러를 시뮬레이션 형태로 만들어 보아요. 여기서 작성할 시뮬레이션은 CPU가 하나 있는 컴퓨터 시스템에서 라운드 로빈 방식의 스케쥴러의 동작을 표현합시다. 스케쥴러는 컴퓨터 내에 여러 개의 프로세스(동작 중인 프로그램)중에서 누가 CPU를 사용할 것인지를 결정하는 운영체제의 핵심 모듈이죠. (참고로 Windows 운영 체제는 스케쥴링 대상이 쓰레드입니다.) 그 중에 라운드 로빈 방식의 스케쥴러는 시스템 내에 정해진 시간(타임 퀀텀)동안 CPU를 사용한 후 다시 대기 큐에 가서 대기하고 맨 앞에 대기하는 프로세스가 CPU를 점유하여 사용하게 운용해요. 여기에서는 프로세스의 상태를 Idel(휴먼 상태), Ready(준비 상태), Run(동작 ..

3.4 큐(Queue) 이번에는 큐를 알아보기로 해요. 큐는 자료를 한쪽으로 보관하고 다른쪽에서 꺼내는 FIFO(First In First Out) 방식의 자료구조입니다. 큐에 자료를 보관하는 연산을 PUT 혹은 ENQUEUE라 말하고 꺼내는 연산을 GET 혹은 DEQUEUE라고 말합니다. 그리고 보관할 위치 정보를 REAR, 꺼낼 위치 정보를 FRONT라고 말해요. 먼저 간단하게 보관하는 큐를 만들어 보기로 해요. class Queue { 여기에서는 자료를 저장할 버퍼를 생성할 때 정하기로 할게요. 버퍼의 위치를 기억할 멤버를 선언하세요. int *buffer; 버퍼의 크기를 기억할 멤버도 필요하겠죠. const int size; 자료를 꺼낼 위치 정보도 기억해야 합니다. int front; 자료를 보..

3.3 스택(Stack) 이번에는 스택을 알아보기로 해요. 스택은 자료를 한쪽으로 보관하고 꺼내는 LIFO(Last In First Out) 방식의 자료구조입니다. 스택에 자료를 보관하는 연산을 PUSH라 말하고 꺼내는 연산을 POP이라고 말합니다. 그리고 가장 최근에 보관한 위치 정보를 TOP 혹은 스택 포인터라 말합니다. 먼저 간단하게 정수를 보관하는 스택을 만들어 보기로 해요. class Stack { 스택에는 자료를 보관할 저장소가 필요합니다. int *buffer; 저장소의 크기를 기억하는 멤버를 선언하세요. const int size; 가장 최근에 보관한 자료의 위치를 인덱스로 기억하는 멤버를 선언하세요. int top; public: 생성자는 스택 크기를 입력 인자로 받게 합시다. Stack..