언제나 휴일

10.2.2 순열 문제 소스 코드 다음은 앞에서 작성한 순열 문제의 소스 코드입니다. //Heuristic.h#pragma once#include #include using namespace std;typedef vector Bucket;typedef Bucket::iterator BIter;typedef Bucket::const_iterator CBIter; class Heuristic;typedef vector Heues;typedef Heues::iterator HIter;typedef Heues::const_iterator CHIter; class Heuristic{ Bucket original; Bucket out;public: Heuristic(Bucket bucket); Heues EnumN..

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.2.2 이중 연결리스트 만들기 이번에는 노드에 링크가 두 개 있는 이중 연결리스트를 만듭시다. 그리고 연결리스트의 head와 tail이 가리키는 노드를 초기에 만들기로 할게요. 링크가 두 개 있으면 이전 노드의 위치 정보를 갖고 있으므로 삭제나 추가할 때 이전 노드의 위치를 기억하는 변수를 별도로 선언할 필요가 없습니다. 그리고 연결리스트 초기화 과정에서 head와 tail이 가리키는 각 노드를 초기에 만들면 자료를 보관하는 노드를 맨 앞이나 맨 뒤에 보관하지 않아 연산을 단순하게 표현할 수 있습니다. 이 부분은 실제 구현하면서 설명하기로 할게요. 참고로 자료를 보관할 목적이 아닌 연결리스트를 운영하기 쉽게 생성한 노드를 더미 노드(Dummy Node)라 부릅니다. 여기서 만들 이중 연결리스트는 he..

3.1.5 vector를 인덱스 연산으로 사용 vector는 확장 가능한 배열로 연속적인 메모리에 자료를 보관하는 자료구조입니다. 연속적인 메모리에 자료를 보관하기 때문에 메모리의 시작 위치에서 상대적 거리를 통해 원하는 요소를 접근하게 프로그래밍하면 접근 비용이 거의 들지 않습니다. 프로그래밍 언어에서 제공하는 배열은 거의 모두 인덱스 연산을 사용하여 배열의 원소에 접근하는 것을 제공하고 있습니다. STL의 vector에서도 인덱스 연산을 제공합니다. 주의할 점은 vector에는 저장소의 크기와 보관한 자료 개수를 기억하는 멤버가 있는데 인덱스 연산으로 사용할 때는 0에서 보관한 자료 개수 -1 까지 사용할 수 있어요. 따라서 보관한 자료에 접근하거나 변경할 때만 사용할 수 있다는 것입니다. 따라서 S..

3.1.2 vector에 순차적으로 보관 작성할 프로그램은 장르 관리 프로그램입니다. 장르에는 장르 번호와 장르명이 있습니다. 장르 번호는 순차적으로 부여하며 장르명은 사용자에게 입력받습니다. 장르 번호와 장르명으로 삭제할 수 있고 검색할 수 있습니다. 그리고 모든 장르 목록을 확인할 수 있습니다. 제공할 기능을 살펴보면 장르 추가, 장르 번호로 장르 삭제, 장르명으로 장르 삭제, 장르 번호로 검색, 장르명으로 검색, 모든 장르 목록 확인이 있어요. vector에 순차적으로 보관할 때는 push_back 메서드를 사용하세요. 원하는 자료를 찾을 때는 반복자를 이용하여 찾거나 find, find_if 알고리즘을 이용하여 찾습니다. 삭제할 때는 자료가 있는 위치를 찾아 erase 메서드를 사용하세요. 모든 ..

3.1.1 이 책에서 공통으로 사용하는 것들 앞으로 이 책에서 사용할 클래스 ehglobal을 소개를 하겠습니다. ehglobal 클래스에는 이 책에 소개되는 전반적인 예제 프로그램에서 공통으로 사용할 만한 함수들을 정적 멤버 메서드로 캡슐화되어 있습니다. 이 책에 공통으로 사용 가능한 것들에 대한 정의에서는 형식 명과 메서드 명 모두 소문자만을 사용하고 있습니다. class ehglobal { public: 콘솔 화면을 지우는 메서드를 제공합시다. static void clrscr();//화면을 지우는 메서드 시간을 지연시키는 메서드도 제공합시다. static void timeflow(int millisecond); //원하는 시간동안 지연시키는 메서드 정수를 입력받는 메서드도 제공합시다. static..

2.2 거품 정렬(Bubble Sort) 이번에는 반복적인 방법으로 해결하는 거품 정렬(Bubble Sort) 알고리즘을 살펴볼게요. 거품 정렬은 앞에서부터 이웃하는 원소의 값을 비교하여 위치를 교환하는 것을 반복해요. 이를 끝까지 수행하면 제일 큰 값이 맨 뒤에 위치합니다. 그리고 정렬할 개수를 1 줄인 후에 다시 반복해요. 정렬할 개수가 1일 때까지 반복하면 정렬 작업이 끝나요. 거품 정렬(base:배열의 시작 주소, n: 원소 개수, compare:비교 논리) 반복(i:=n->1) 반복(j:=1->i) 조건(compare(base[j-1], base[j]) > 0) 교환(base[j-1],base[j]) 예: 2 9 4 1 5 6 8 3 7 (정렬 전, n:9) 2 9 4 1 5 6 8 3 7 (i..

2. 반복 알고리즘 문제를 해결하는 다양한 방법 중에서 반복적인 방법으로 문제를 해결하는 것은 매우 흔합니다. 이번 장에서는 반복적인 방법으로 문제를 해결하는 반복 알고리즘을 다룰게요. 특히 반복 알고리즘으로 어떠한 문제를 해결할 수 있다는 것을 증명하기 위해서는 어떠한 특징을 고려해야 하는지 살펴볼 거예요. 반복 알고리즘으로 어떠한 문제를 해결할 수 있는지 증명할 때는 루프 변성과 루프 불변성을 이용합니다. 루프 변성은 반복문을 수행하면서 변하는 성질이며 루프 불변성은 변하지 않는 성질이예요. 예를 들어 정수 start에서 end 사이의 합계를 구하는 문제가 있다고 가정할게요. 이 문제는 다음과 같은 방법으로 해결할 수 있어요. 특정 범위의 합계 구하기(start:시작 값, end: 끝 값) sum:=..

1.2 알고리즘 소개 알고리즘은 특정 문제를 해결하기 위한 논리를 말해요. 해결해야 할 어떠한 문제가 주어지면 문제에 주어지는 선행 조건과 영향 인자와 후행 조건을 알아겠죠. 선행 조건은 알고리즘을 수행 하기 전의 상태를 말합니다. 그리고 영향 인자는 문제를 해결하는데 영향을 주는 인자예요. 후행 조건은 문제를 해결하고 난 후의 상태를 말해요. 결국 알고리즘은 선행 조건인 상태에서 주어진 영향 인자를 가지고 후행 조건에 맞게 문제를 해결하는 것이죠. 예를 들어 특정 범위 내의 정수의 합계를 구하는 문제를 살펴봅시다. 이 때는 선행 조건은 특별한 것이 없네요. 문제를 해결하는 데 영향을 주는 인자는 범위의 시작과 끝이겠죠. 따라서 알고리즘을 함수로 구현한다면 입력 인자로 범위의 시작 정수와 끝 정수가 필요..

1.1 자료구조와 STL 자료구조는 자료를 메모리에 표현하는 구조를 말하며 크게 선형 자료구조와 비 선형 자료구조로 나눠요. 선형 자료구조에는 같은 종류의 자료를 연속적인 메모리에 관리하는 배열과 데이터와 링크로 구성하는 노드들의 선형 집합인 연결리스트가 있어요. 그리고 임시적으로 자료를 보관하는 버퍼로 가장 최근에 보관한 자료를 꺼내주는 스택(Last In First Out)과 가장 먼저 보관한 자료를 꺼내주는 큐(First In First Out)도 선형 자료구조인 배열이나 연결리스트를 이용한 잘 알려진 버퍼입니다. 비 선형 자료구조에는 나무의 뿌리처럼 자료를 보관하는 모습을 계층적으로 표현할 수 있는 트리와 정점과 간선으로 표현하는 그래프 등이 있어요. 이 책에서는 이러한 자료구조들을 소개하고 표준..