언제나 휴일

7.5 STL의 map 사용이번에는 STL의 map 사용 방법을 알아보기로 합시다. map은 key와 value를 쌍으로 구성하는 pair를 보관하는 구조입니다. key를 기준으로 자료를 보관하고 검색하며 실질적으로 보관할 자료를 value입니다. 이처럼 키와 값을 쌍으로 보관하는 자료구조를 사전 컬렉션이라고도 부릅니다. 만약 회원 관리 프로그램에서 회원의 id를 기준으로 map에 보관하면 다음처럼 string을 키로 하고 Member *를 value로 하는 pair를 보관합니다.#include using std::map;using std::pair;typedef map Mdic; 여기에서는 map을 사용하는 방법을 두 가지 방법으로 나누어 설명할게요. 첫 번째 방법은 insert, find, erase..

7.4 이진 탐색 트리 구현이제 앞에서 설계한 이진 탐색 트리를 구체적으로 구현합시다. 먼저 이진 탐색 트리의 추가 기능인 AddBook 메서드를 구현하기로 해요.bool BinSearchTree::AddBook(int bnum,string title){먼저 주요 키인 도서 번호로 부모 노드를 검색하기로 해요. Node *parent = Find(root,bnum); if(parent) {검색한 부모의 키가 입력한 도서 번호와 일치하였는지 확인하세요. Book *sbook = parent->book; if(sbook->GetBNum() == bnum) {일치하면 도서를 보관하지 않고 추가 실패를 반환하세요. return false; } }입력받은 인자로 도서 개체를 생성하세요. Book *book = n..

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

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..

3.2.1 단순 연결리스트 만들기 이번에는 간단하게 단순(단일) 연결리스트를 만들어 보아요. 여기에서 만드는 단순 연결리스트는 개념을 잡기 위해 만드는 것으로 노드에 보관할 자료 형식을 정수로 한정할게요. 뒤에서 STL을 모델로 list를 만들 때 어떠한 자료 형식도 보관할 수 있게 만들거예요. 제공할 기능은 생성자, 해제화, 맨 뒤에 보관, 맨 앞에 보관, 원하는 위치에 보관, 탐색 가능한 반복자 제공, 데이터 제거, 데이터 보관 유무 확인, 전체 보기 기능입니다. 단순 연결리스트를 정의할 클래스 이름을 SimpleLinkedList라 정합시다. class SimpleLinkedList { 단순 연결리스트의 노드는 데이터와 다음 노드의 위치 정보를 기억하는 링크로 구성합니다. 노드는 연결리스트에서 접근..

2.4 삽입 정렬(Insertion Sort) 이번에는 반복적인 방법으로 해결하는 삽입 정렬(Insertion Sort) 알고리즘을 살펴볼게요. 삽입 정렬도 순차 정렬처럼 맨 앞에서부터 정렬 범위를 확장해 나가는 알고리즘이예요. 차이점은 확장할 범위의 끝에 있는 원소를 앞의 원소와 비교하며 자신보다 크면 위치를 바꾸고 그렇지 않으면 반복을 멈춘다는 것이죠. 순차 정렬에서 확장할 위치에 배치할 원소를 뒤쪽 원소와 비교하며 교환했지만 삽입 정렬에서는 확장할 위치에 있는 원소를 앞의 원소와 비교하며 교환하며 자신의 위치를 찾는다는 것이 다릅니다. 삽입 정렬(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리) 반복(i:=1->n) 반복(j:=i->1) 조건(compare(base[j-1],..