본문 바로가기

Programming

HashMap.h : 해싱을 이용하는 맵 클래스 #오류 있음 #pragma once#ifndef ___HashMap#define ___HashMap// HashMap.h : 해싱을 이용하는 맵 클래스#include "HashRecord.h"#include "hashFunctions.h" class HashMap {// 해시 맵 클래스 선언Recordtable[TABLE_SIZE];// 해싱 테이블. 크기는 13public:HashMap() { reset(); }// 생성자. 모든 버켓을 비움void reset() {// 모든 버켓을 비움for (int i = 0; i < TABLE_SIZE; i++)table[i].reset();} // 맵의 전체 내용을 출력void display() {for (int i = 0; i < TABLE_SIZE; i++) {print.. 더보기
HashRecord.h : 해시 맵을 위한 keyed Record 클래스 #pragma once#ifndef ___HashRecord#define ___HashRecord// HashRecord.h : 해시 맵을 위한 keyed Record 클래스#include #include #include using namespace std;#define KEY_SIZE 64// 탐색키의 최대길이#define VALUE_SIZE 64// 탐색키와 관련된 정보 class Record {char key[KEY_SIZE];// 키 필드(사전의 경우 "단어")char value[VALUE_SIZE];// 키와 관련된 자료 ("의미")public:Record(const char* k = "", const char*v = "") { set(k, v); }void set(const char* k, c.. 더보기
해싱의 오버플로우 처리 방법 해싱의 오버플로우 처리 방법 해싱에서 오버플로우를 잘 처리하는 것은 매우 중요하다. 이러한 오버플로우의 처리 방법은 다음의 두 가지로 나눌 수 있다. (1) 선형 조사법(linear probing) : 충돌이 일어나면 해시 테이블의 다른 위치를 찾아 항목을 저장한다. (2) 체이닝(chaining) : 해시 테이블의 하나의 위치가 여러 개의 항목을 저장할 수 있도록 해시 테이블의 구조를 변경한다. 선형 조사법 선형 조사법(linear probing) 은 해싱 함수로 구한 버켓에 빈 슬롯이 없으면 그 다음 버켓에서 빈 슬롯이 있는지를 찾는 방법이다. 이때 비어 있는 공간을 찾는 것을 조사(probing) 이라고 하는데, 여러 가지의 조사 방법이 가능하다. 만약 ht[k] 에서 충돌이 방생했다고 하자. 선형.. 더보기
해싱 해싱 해싱은 키값을 비교하는 것이 아니라 탐색키에 산술적인 연산을 적용하여 항목이 저장되어 있는 위치, 즉 인덱스를 직접 계산하는 방식이다. 이렇게 키값의 연산에 의해 직접 접근이 가능한 구조를 해시 테이블(hash table)이라 하며, 해시 테이블을 이용한 탐색을 해싱(hashing)이라 한다. 예를 들어 탐색키들이 모두 1 ~ 1000 사이의 정수라고 가정해보자. 그렇다면 가장 빠르게 자료를 저장하고 꺼낼 수 있는 방법은 1000개의 요소를 가지는 배열을 만드는 것이다. 자료의 삽입과 탐색은 탐색키를 배열의 인덱스로 생각하고 단지 배열의 특정 요소를 읽거나 쓰면 된다. 이들 연산은 명백하게 이다. 이것이 해싱의 기본 아이디어이다. 현실적으로는 탐색키들이 문자열이거나 굉장히 큰 숫자이기 때문에 탐색키.. 더보기
AVL 트리 AVL 트리 AVL 트리는 Adelson - Velskii와 Landis에 의해 제안된 트리로 각 노드에서 왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이 차리가 1 이하인 이진 탐색 트리를 말한다. 이 트리는 트리가 비균형 상태로 되면 스스로 노드들을 재배치하여 균형 상태로 만든다. AVL 틀는 항상 균형 트리를 보장하기 때문에 의 탐색 시간을 보장한다. 삽입과 삭제 연산도 시간 안에 할 수 있다. AVL 트리도 탐색에서는 일반 이진 탐색 트리의 탐색 연산과 동일하다. 따라서 시간 복잡도는 이다. AVL 트리에서 균형이 깨질 수 있는 연산은 삽입과 삭제 연산이다. AVL 트리의 삽입 연산 이진 탐색 트리에서 노드가 삽입되면 삽입되는 위치에서 루트까지의 경로에 있는 모든 조상 노드들의 균형 인수가 영향을 .. 더보기
균형 이진 탐색 트리 균형 이진 탐색 트리 맵은 이진 탐색 트리로도 구현할 수 있다. 이진 탐색과 이진 탐색 트리는 근본적으로 같은 원리에 의한 탐색 구조로 탐색에 걸리는 시간도 로 동일하다. 그렇다면 이들의 차이는 무엇일까? 답은 자료의 삽입과 삭제의 용이성에 있다. 이진 탐색에서 자료는 배열에 저장되어 있으므로 삽입과 삭제가 상당히 힘들다. 즉, 맵에 자료를 삽입하거나 삭제할 때 불필요한 항목들의 많은 이동이 필요하다. 반면에 맵을 이진 탐색 트리로 구현하면 시간에 삽입과 삭제가 가능하다. 따라서 삽입과 삭제가 빈번히 이루어진다면 반드시 이진 탐색 트리를 사용하여야 한다. 이진 탐색 트리는 만약 균형 트리이면 의 탐색 연산 시간 복잡도를 갖는다. 그러나 삽입과 삭제 연산이 이진 탐색 트리를 유지시키기는 하지만 균형 트리를.. 더보기
Search.h : 다양한 탐색 함수를 포함함 헤더 색인 순차 탐색색인 순차 탐색(indexed sequential search) 방법은 인덱스(index)라 불리는 테이블을 사용하여 탐색의 효율을 높이는 방법이다. 인덱스 테이블은 주 자료 리스트에서 일정 간격으로 발췌한 자료를 가지고 있다. 인덱스 테이블에 m개의 항목이 있고, 주 자료 리스트의 데이터 수가 n이면 각 인덱스 항목은 주 자료 리스트의 각 n/m 번째 데이터를 가지고 있다. 이 때 주 자료 리스트와 인덱스 테이블은 모두 정려되어 있어야 한다. 색인 순차 탐색 알고리즘은 우선 인덱스 테이블에서 index[i] 더보기
Sorting.h : 다양한 정렬을 포함한 헤더 | 정렬 방법의 성능 비교 알고리즘 최선 평균 최선 삽입 정렬 선택 정렬 버블 정렬 셸 정렬 퀵 정렬 힙 정렬 합병 정렬 기수 정렬 | 정렬 알고리즘별 실험 결과 ( 정수 : 60,000개 ) 알고리즘 실행 시간( 단위 : sec) 삽입 정렬 7.348 선택 정렬 10.842 버블 정렬 22.894 셸 정렬 0.056 힙 정렬 0.034 합병 정렬 0.026 퀵 정렬 0.014 #pragma once#ifndef ___Sorting#define ___Sorting// Sorting.h : 다양한 정렬을 포함한 헤더#include "cstdio"#include "cstdlib"#include "CircularQueue.h" #define MAX_SIZE 1024#define BUCKETS 10#define.. 더보기

티스토리툴바