언제나 휴일

9.2 스택을 이용한 수식 파서수학에서 수식은 피연산자 사이에 연산 기호를 표기하는데 이를 중위 표기라 얘기합니다. 그런데 컴퓨터 프로그램에서 중위 표기의 수식을 계산할 때 순차적으로 수행하면 수학에서의 연산 결과가 다르게 나옵니다. 예를 들어 2+3*5의 연산은 +연산보다 *연산을 먼저하기 때문에 17이지만 순서대로 연산을 수행하면 2+3을 수행한 후에 5*5를 수행해서 25가 나옵니다. 컴퓨터 프로그램에서 제대로 수식을 계산하기 위해서는 우선 순위에 맞게 연산의 순서를 파악한 후에 계산해야 합니다. 수식을 연산 순서에 맞게 표현하는 방법 중에 연산 기호의 자식으로 피연산자를 도식하는 수식 파서 트리를 이용해서 설명해 볼게요. 2+3*5 수식에서 +연산의 피연산자는 2와 3*5의 연산 결과입니다. 그리..

9.1 힙 정렬 알고리즘이제 힙 정렬 알고리즘을 살펴보기로 해요. 힙 정렬은 완전 이진 트리의 한 종류인 힙 트리를 이용하여 정렬하는 알고리즘입니다. 먼저 힙 트리가 무엇인지 살펴본 후에 힙 정렬 알고리즘을 알아보고 분석 및 구현해 봅시다. 힙 트리는 부모의 값이 자식의 값보다 큰 값을 보장하는 최대 힙과 작은 값을 보장하는 최소 힙이 있습니다. 최대 힙으로 표현한 힙 트리의 루트에는 가장 큰 값을 갖고 최소 힙으로 표현하면 가장 작은 값을 갖습니다. 힙 트리처럼 완전 이진 트리는 배열로 많이 표현합니다. 완전 이진 트리가 아닌 이진 트리도 배열로 표현할 수 있지만 트리의 높이가 높아지고 한 쪽으로 기울어질 수록 비어있는 공간이 많아져서 메모리 효율이 떨어집니다. 하지만 완전 이진 트리는 마지막 자료가 ..

9. 기타 이진 트리 및 분할 정복 이번에는 기타 이진 트리와 분할 정복에 관해 알아봅시다. 트리는 용도에 따라 매우 다양한 형태를 지닙니다. 여기에서는 힙 정렬 알고리즘을 소개하면서 힙 트리를 다루고 수식 계산기에 사용하는 수식 파서 트리를 살펴볼게요. 그리고 문제를 분할한 후에 작은 문제를 해결하는 과정을 통해 전체 문제를 정복해 나가는 병합 정렬 알고리즘을 살펴볼 거예요. 병합 정렬 알고리즘에서 정렬할 배열을 분리하는 부분은 재귀적인 방법을 사용할 수 있어 분할 정복 알고리즘은 재귀 알고리즘으로 분류할 수 있습니다. 힙 트리는 완전 이진 트리로 노드를 이용하여 구현하는 것보다 배열을 이용하여 구현하는 것이 효과적입니다. 여기서는 자신의 부모 인덱스와 자식 인덱스를 계산할 수 있어야 하는데 이들에 대..

8.7 장르별 도서 관리 프로그램 코드 다음은 이번 실습에서 작성한 장르별 도서 관리 프로그램의 소스입니다. //ehglobal.h#pragma once#pragma warning(disable:4996)#include #include using namespace std; #include #include enum keydata{ NO_DEFINED,F1,F2,F3,F4,F5,F6,F7,F8,F9,F10,ESC}; //공통적으로 사용할 정적 메서드를 캡슐화한 클래스class ehglobal{public: static void clrscr();//화면을 지우는 메서드 static void timeflow(int millisecond); //원하는 시간동안 지연시키는 메서드 static int getnum()..

8.6 도서 삭제 및 소멸 마지막으로 도서 삭제 기능과 소멸자를 구현합시다.void App::RemoveBook() //도서 삭제{장르를 선택하세요. Genre *genre = SelectGenre(); if(genre == 0) {잘못 선택하였으면 메시지를 출력하고 종료합니다. cout

8.6 도서 삭제 및 소멸마지막으로 도서 삭제 기능과 소멸자를 구현합시다.void App::RemoveBook() //도서 삭제{장르를 선택하세요. Genre *genre = SelectGenre(); if(genre == 0) {잘못 선택하였으면 메시지를 출력하고 종료합니다. cout

8.5 도서 검색 및 특정 장르 보기이번에는 ISBN으로 도서 검색과 특정 장르 선택 후 도서 검색과 특정 장르 보기 기능을 구현합시다. 먼저 ISBNㅇ로 도서 검색 기능을 구현하세요.void App::FindBookByISBN() //ISBN으로 도서 검색{먼저 검색할 도서의 ISBN을 입력받으세요. cout

8.4 전체 도서 보기 및 전체 보기이번에는 전체 도서 보기와 전체 보기 기능을 구현합시다. 앞에서 도서 추가 기능을 구현하였는데 이를 확인할 수 있기 때문에 먼저 구현하는 것이 개발하기 편합니다. 먼저 정체 도서 보기 기능을 구현합시다.void App::ListBook() //전체 도서 보기{isbn을 키, 도서 개체를 값으로하는 bookdic의 반복자를 이용하여 전체를 순회합니다. BDIter seek = bookdic.begin(); BDIter last = bookdic.end(); Book *book=0; for( ;seek != last; ++seek) {map에 보관한 것은 isbn키와 도서 개체를 값으로 하는 pair입니다. 도서 개체를 구하려면 반복자에 간접 연산하여 보관한 pair에 접..

8.3 도서 추가이번에는 도서 추가 기능을 구현합시다. void App::AddBook() //도서 추가{먼저 추가할 도서의 ISBN을 입력받습니다. coutGetGNum() == gnum) {장르의 번호와 사용자가 입력한 장르 번호가 같으면 장르를 반환하세요. return genre; } }사용자가 입력한 장르 번호를 갖는 장르 개체가 없으면 0을 반환하세요. return 0;} Genre 클래스에 도서 추가 AddBook 메서드와 장르 번호 접근자 GetGNum을 추가하세요.class Genre{ ...중략... Book *AddBook(string isbn); int GetGNum()const;}; Book *Genre::AddBook(string isbn){사용자에게 장르 내 도서 구분자를 입력받..

8.2 장르 추가 및 전체 장르 보기이번에는 장르 추가 및 전체 장르 보기를 구현합시다. 시나리오를 보면 장르 추가에서 장르의 일련 번호는 1부터 순차 부여합니다. 이를 위해 App 개체는 가장 최근에 생성한 장르 번호를 기억하고 있어야 합니다. 멤버 필드로 가장 최근에 장르 번호를 추가하세요.class App{ ...중략... int last_gnum; ...중략...}; App 생성자에서는 last_gnum을 초기값을 설정하세요.App::App(void){ last_gnum = 0;}void App::AddGenre() //장르 추가{장르 추가에서는 부여할 장르 번호를 위해 last_gnum을 1 증가하세요. last_gnum++;사용자로부터 추가할 장르 이름을 입력받습니다. cout