본문 바로가기

전체 글149

[파일구조] - 인덱스 파일의 구현 I 이 글의 소스 코드는 File Structures: An Object-Oriented Approach with C++ 3rd Edition의 내용을 수정하여 작성한 것 입니다. 1. Class TextIndex 인덱스 파일을 구현하기에 앞서, TextIndex라는 인덱스를 저장하는 자료구조를 정의한다. TextIndex는 일정 수의 인덱스들을 저장하는 자료구조로써, 인덱스의 추가, 제거, 검색 등의 연산을 갖는다. TextIndex의 class 정의는 아래와 같다. class TextIndex { public: TextIndex(int maxKeys = 100, bool unique = true); ~TextIndex(); int Insert(const char *key, int recAddr); int.. 2016. 6. 10.
[파일구조] - 인덱싱(Indexing) 1. Entry Sequenced File Entry sequenced file은 레코드가 입력되는 순서대로 저장되는 파일이다. 레코드가 입력되는 순서대로 파일에 저장되기 때문에 파일에 저장된 레코드들은 정렬되어있지 않다. 파일에 저장된 레코드들이 정렬되어있지 않기 때문에 어떤 레코드를 찾기 위해서는 파일의 앞쪽부터 순차적으로 레코드를 읽어야한다. Entry sequenced file은 데이터를 관리한다는 측면에서는 매우 비효율적인 구조이다. Entry sequenced file의 이러한 문제점을 해결하기 위해 레코드가 입력될 때마다 레코드들을 정렬하는 sorted file을 생각할 수 있지만, sorted file에는 아래와 같은 치명적인 문제점이 존재한다. 레코드가 입력될 때 파일을 정렬한다면, 레코.. 2016. 6. 8.
큐(Queue) 1. 개요 큐(queue)는 먼저 입력된 자료가 먼저 출력되는 First In First Out(FIFO)구조로 동작하는 자료구조를 의미한다. 나중에 입력된 자료가 먼저 출력되는 스택(stack)과는 반대되는 구조이다. 운영체제에서 스택은 프린터 작업 처리, 프로세스 관리 등 데이터나 요청이 입력된 순서대로 작업을 처리해야하는 상황에 주로 이용된다. 큐에는 선형 큐(linear queue), 환형 큐(circular queue), 링크드 큐(linked queue) 등이 있다. 일반적으로, 큐는 선형 큐를 의미하며 선형 큐의 문제점을 극복하기 위해 환형 큐, 링크드 큐 등이 고안되었다. 선형 큐의 문제점은 아래에서 자세하게 설명한다. 2. 선형 큐(Linear Queue) 선형 큐는 큐의 가장 단순한 형.. 2016. 5. 22.
스택 (Stack) 1. 개요 스택 (stack)은 한쪽 끝에서만 자료를 추가하거나 꺼낼 수 있는 자료구조이다. 스택은 Last In First Out (LIFO)의 구조로 동작하기 때문에 스택에 접근할 때는 가장 최근에 추가된 자료부터 읽는다. 스택에 자료를 추가하는 연산을 push, 자료를 꺼내는 연산을 pop이라고 한다. [그림 1] 스택의 동작 스택은 많은 프로그램에서 광범위하게 사용되고 있는 자료구조로써, 가장 대표적인 활용으로는 시스템 스택이 있다. 다소 복잡해보일 수도 있는 함수 호출이나 재귀적 실행을 스택이라는 자료구조를 통해 간단히 구현할 수 있다. 아래의 [코드 1]은 main에서 func1을 호출하고 func1에서는 func2를, func2에서는 func3를 호출하도록 동작한다. 그러나 실질적인 프로그램.. 2016. 5. 21.
[머신러닝] - Overfitting (과적합) 1. 개요 머신 러닝 (machine learning)에서 overfitting은 학습데이터를 과하게 잘 학습하는 것을 뜻한다. 일반적으로 학습 데이터는 실제 데이터의 부분집합인 경우가 대부분이다. 따라서, 아래의 그래프처럼 학습 데이터에 대해서는 오차가 감소하지만, 실제 데이터에 대해서는 오차가 증가하는 지점이 존재할 수 있다. Overfitting을 이러한 관점에서 본다면 overfitting은 학습 데이터에 대해 과하게 학습하여 실제 데이터에 대한 오차가 증가하는 현상이다. 예를 들어, 노란색 고양이를 보며 고양이의 특성을 학습한 사람이 검은색이나 흰색 고양이를 보고는 그것을 고양이라고 인식하지 못 하는 현상이 overfitting과 유사한 경우이다. 2. Overfitting과 딥러닝 앞에서 설명.. 2016. 5. 7.
[파일구조] - 레코드 검색 1. 순차 탐색(Sequential Search)과 이진 탐색(Binary Search) 검색은 파일에서 가장 빈번하게 발생하는 연산이다. 따라서, 파일구조를 설계할 때는 파일 검색 연산을 신중히 구현해야 한다. 파일을 검색하기 위한 방법에는 크게 순차 탐색(sequential search)과 이진 탐색(binary search)이 있다. 순차 탐색의 시간 복잡도는 $O(n)$이며, 이진 탐색 트리에서 이진 탐색을 수행할 때의 시간 복잡도는 $log_2(n)$이다.일반적으로 순차 탐색보다 이진 탐색의 효율이 더 좋지만 이진 탐색은 데이터가 정렬되어 있어야 한다는 제약 조건이 존재한다. 또한, 가변 길이 레코드 파일에서 이진 탐색을 수행하기 위해서는 파일의 중간 지점을 찾는 방법에 대한 구현도 필요하다. .. 2016. 4. 24.
[파일구조] - 레코드 관리 1. 레코드 삭제 파일을 이용하다보면 특정 레코드를 삭제하는 경우가 발생한다. 만약 삭제된 레코드가 파일의 가장 끝에 있는 레코드가 아니라면, 삭제된 레코드가 있었던 공간을 재사용하기 위한 방법이 필요하다. 레코드가 있었던 공간을 재사용하기 위해서는 가장 먼저 삭제된 레코드가 어디에 있었는지를 알고 있어야 한다. 2. Available List Available list는 파일에서 사용 가능한 공간을 저장하고 있는 데이터 집합이다. Available list는 스택(stack), 연결 리스트(linked list) 등의 자료구조를 이용하여 구현할 수 있다. 파일구조에서 available list의 구현에 대한 고려사항은 available list의 저장 위치이다. Available list를 저장할 수 .. 2016. 4. 24.
[파일구조] - 레코드 접근과 성능 1. 순차 접근(Sequential Access) 원하는 레코드를 찾기 위해 파일의 현재 위치에서 차례대로 탐색을 실시하는 접근 방법이다. 특별한 구현이 없다면, 레코드를 접근할 때마다 디스크를 물리적으로 움직여야하기 때문에 매우 비효율적이다.순차 접근의 비효율성을 줄이기 위해 레코드 블록화(record blocking) 기법을 이용한다. 블록(block)은 여러 레코드의 집합이며, 파일 시스템은 레코드를 하나씩 읽어 메모리에 적재하는 것이 아니라 디스크에서 블록 단위로 데이터를 읽어 메모리에 적재한다. 예를 들어, 4,000개의 레코드로 구성된 파일을 블록 크기 16인 파일 시스템이 모두 읽기 위해서는 250번의 디스크 접근만 수행하면 된다. 레코드 블록화 기법에서 블록의 크기가 커지면 커질수록 디스크.. 2016. 4. 24.
[파일구조] - 파일과 소프트웨어 1. 추상 데이터 모델(Abstract Data Model) 음악, 이미지, 문서, 설정파일 등의 파일은 레코드와 필드의 집합이라는 개념에서 해석하기에는 다소 맞지 않는 부분이 존재한다. 음악, 이미지, 문서, 설정파일 등과 같은 파일을 레코드와 필드의 집합이 아니라 하나의 객체로 정의하기 위한 개념이 추상 데이터 모델(abstract data model)이다. 추상 데이터 모델은 데이터에 대한 개념적인 정의로써, 데이터 모델 자체에 데이터뿐만 아니라 데이터를 해석하기 위한 구조까지 포함하고 있는 데이터 모델을 뜻한다. 추상 데이터 모델의 가장 큰 특징은 데이터 모델 자체에 데이터를 해석하기 위한 구조를 포함하고 있기 때문에 저장 장치나 프로그래밍 환경에 독립적이라는 것이다.추상 데이터 모델은 데이터의 .. 2016. 4. 24.
[파일구조] - 파일구조 설계 III 이 글의 소스 코드는 File Structures: An Object-Oriented Approach with C++ 3rd Edition의 내용을 수정하여 작성한 것 입니다. 1. 파일에 대한 해석 지금까지 데이터 클래스 내부에 연산을 구현하는 방식부터 추상화(abstraction)와 클래스 계층구조(class hierarchy)를 이용하는 방식까지 다양한 방식으로 파일구조를 설계하였다. 설계에서 가장 중요한 점은 설계의 목적을 잊지 않는 것이다. 파일구조를 설계하는 목적은 결국 파일에 데이터를 저장하고 읽기 위함이다. 따라서, 파일이라는 것에 대한 명확한 정의를 내릴 필요가 있는데, 앞의 글에서 설명한 바와 같이 파일의 정의는 파일구조의 설계에 따라 달라진다. 지금까지 구현한 방식에 따라 파일은 아래.. 2016. 4. 24.
[파일구조] - 파일구조 설계 II 이 글의 소스 코드는 File Structures: An Object-Oriented Approach with C++ 3rd Edition의 내용을 수정하여 작성한 것 입니다. 1. 데이터 클래스의 확장 앞의 글에서 데이터 클래스에 직접 파일 연산을 구현하는 것과 버퍼 클래스를 이용하는 것의 문제점을 서술하였다. 클래스에 직접 파일 연산을 구현하는 방식의 단점을 극복하기 위해 버퍼 클래스를 따로 구현하였지만, 버퍼 클래스를 이용하는 방식 또한 메인 함수에 데이터 클래스의 pack, unpack 과정이 모두 드러나는 문제점이 존재하였다. 버퍼 클래스를 이용하면서 메인 함수를 간단하게 만들기 위한 방법은 매우 간단하다. 바로 버퍼 클래스의 pack, unpack 함수를 호출하는 연산을 데이터 클래스 내부에 .. 2016. 4. 24.
[파일구조] - 파일구조 설계 I 이 글의 소스 코드는 File Structures: An Object-Oriented Approach with C++ 3rd Edition의 내용을 수정하여 작성한 것 입니다. 1. 데이터 클래스 내부에 연산 구현 앞의 글에서 필드와 레코드를 저장하는 다양한 방식을 소개했다. 각각의 방식은 구현 목적과 실행 환경에 따라 장단점이 존재하기 때문에 좋은 파일구조는 다양한 저장 방식을 지원해야 한다. 다양한 저장 방식을 지원하도록 파일구조를 구현하기 위해 가장 쉽게 생각해볼 수 있는 방법은 데이터 클래스 내부에 read/write 연산을 구현하는 것이다. 예를 들어, 아래의 코드처럼 Person 클래스에 고정 길이, 길이 지시자 등의 방식으로 레코드를 읽는 read/write 연산을 구현할 수 있다. 아래의 .. 2016. 4. 23.

티스토리툴바