본문 바로가기

Programming

Chapter1 - 데이터베이스 언어 데이터베이스 언어 데이터베이스 시스템은 데이터베이스 스키마를 기술하는 데이터 정의 언어(Data Definition Language : DDL) 와 데이터베이스 질의 및 갱싱을 표현하는 데이터 조작 언어(Data Manipulation Language : DML) 를 제공한다. 실제로, 데이터 정의 언어와 데이터 조작 언어의 경계는 명확히 구분되어 있지 않다. 오늘날 널리 쓰리고 있는 질의어인 SQL에서 이들 두 언어는 단일 데이터베이스 언어의 한 부분을 이룬다. 데이터 조작 언어데이터 조작 언어(Data Manipulation Language : DML) 는 사용자가 적절한 데이터 모델로 구성된 데이터를 접근하거나 조작할 수 있도록 하는 언어이다. 접근의 형태는 다음과 같다. 데이터베이스 내에 저장된 .. 더보기
Chapter 1 - 데이터 관점 데이터 관점 DBMS는 서로 관련이 있는 파일의 모임과 사용자로 하여금 이 파일들을 액세스하거나 수정하도록 하는 프로그램의 집합이다. 데이터베이스 시스템의 주요한 목적은 사용자에게 데이터에 관한 추상적인 관점을 제공하는 것이다. 즉, 시스템은 데이터가 어떻게 저장되고 유지되는지에 관한 세부 사항은 사용자로부터 은폐한다. 데이터의 추상화시스템이 원활하게 사용되려면, 데이터 검색이 효율적으로 이루어져야 한다. 이러한 목적을 이루기 위해, 데이터베이스 내의 데이터를 효율적으로 표현하기 위한 여러 가지 복잡한 데이터 구조가 제안되었다. 많은 데이터베이스 시스템의 경우 사용자의 대부분이 컴퓨터를 잘 다루지 못하는 일반 사람들이므로, 여러 단계의 추상화를 통해 이러한 복잡한 구조를 되도록이면 감추어, 사용자의 이해.. 더보기
Chapter1 - 데이터베이스 시스템의 목적 데이터베이스 관리 시스템(DBMS) 은 서로 관계 있는 데이터들의 모임과 그 데이터에 접근하기 위한 프로그램 (application) 의 집합으로 구성된다. 데이터베이스(database) 는 보통 이 데이터들의 모임을 일컫는 말로서, 흔히 조직과 관련된 정보들을 포함한다. DBMS 의 주요 목적은 데이터베이스에 정보를 저장하고 또 이를 검색하기 윈한 편리하고도 효율적인 환경을 제공하는 데 있다. 데이터베이스는 대규모의 정보를 관리하도록 설계된다. 데이터의 관리에는 정보 저장 구조를 정의하는 작업과 저장된 정보를 조작하기 위한 기법을 제공하는 작업 모두가 포함된다. 또, 데이터베이스 시스템은 저장된 정보를 시스템 고장이나 모든 불법적은 액세스 등으로부터 안전하게 보호해야 한다. 데이터가 여러 사용자간에 공.. 더보기
STL 맵 클래스의 활용 : 영어 단어장 STL 맵 클래스의 활용 : 영어 단어장 표준 템플릿 라이브러리는 맵 클래스를 제공한다. 맵은 탐색을 위한 자료구조로 지금까지 맵을 구현할 수 있는 다양한 방법을 공부했다. 우리는 STL 의 맵이 어떤 방법으로 구현되었는지는 관심을 갖지 않는다. 그리고 탐색을 수행하는 자료의 특성에 따라 효율적으로 구현하는 방법이 달라질 수 있다. 이 절에서는 STL의 맵을 사용하기 위해서는 해싱이나 이진 탐색 트리를 고려할 필요 없이 다음과 같이 헤더파일을 포함시키는 것만으로 충분하다. #include using namespace std; 맵에서는 기본적로 키(key) 와 값(value)이 정의되어야 한다. STL의 맵에서도 마찬가지로, 키를 위한 자료형과 값을 위한 자료형을 정해야 한다. 우리는 영어 단어장을 만들 .. 더보기
해싱의 성능 분석 해싱의 성능 분석 해싱의 시간 복잡도는 이다. 그러나 이것은 충돌이 전혀 일어나지 않는 상황에서만 가능하다. 따라서 실제 해싱의 탐색 연산은 보다는 느려지게 된다. 해싱의 성능을 분석하기 위해 해시 테이블이 얼마나 채워져 있는지를 나타내것을 적재 밀도(loading density) 또는 적재 비율(loading factor) 라 한다. * n = 저장된 항목의 개수, M = 해싱 테이블의 버켓의 개수 가 0 이면 해시 테이블은 비어있다. 의 최댓값은 충동 해결 방법에 따라 달라지는데, 선형 조사법에서는 테이블이 가득하면 모든 버켓에 하나의 항목이 저장되므로 1이 된다. 체인법에서는 저장할 수 있는 항목의 수가 해시 테이블의 크기를 넘어설 수 있기 때문에 는 최댓값을 가지지 않는다. 기존의 연구 결과들을 .. 더보기
HashChainMap.h : 해시 체이닝으로 구현된 해시 맵 #pragma once#ifndef ___HashChainMap#define ___HashChainMap// HashChainMap.h : 해시 체이닝으로 구현된 해시 맵 #include "HashNode.h"#include "hashFunctions.h" class HashChainMap {Node* table[TABLE_SIZE];public:HashChainMap() { for (int i = 0; i getLink())print.. 더보기
HashNode.h : 해시 맵을 위한 노드 클래스 #pragma once#ifndef ___HashNode#define ___HashNode// HashNode.h : 해시 맵을 위한 노드 클래스#include "HashRecord.h" class Node : public Record {Node* link;// 다음 노드를 가리키는 포인터 함수public:Node(const char* key, const char* val): Record(key, val), link(NULL) {}Node* getLink() { return link; }void setLink(Node* next) { link = next; }};#endif // !___HashNode 더보기
이차 조사법, 이중 해싱법, 체이닝 이차 조사법이차 조사법(quadratic probing) 은 선형 조사법과 유사하지만 충돌 방생 시 다음에 조사 할 위치를 다음 식에 의하여 결정한다. (h(k) + i*i) mod M for i = 0,1, ... , M-1 따라서 조사되는 위치는 다음과 같다. h(k), h(k) + 1, h(k) + 4, h(k) + 9, ..... mod M 여기서 주의할 것은 모든 위치를 조사하게 만들려면 여전히 테이블 크기는 소수여야 한다는 점이다. 이 방법은 선형 조사법에서의 문제점인 군집화 현상을 크게 완화시킬 수 있다. 이 방법도 2차 집중 문제를 일으킬 수 있지만 1차 집중처럼 심각한 것은 아니다. 2차 집중의 이유는 동일한 위치로 사상되는 여러 탐색키들이 같은 순서에 의하여 빈 버켓을 조사하기 때문이다.. 더보기

티스토리툴바