📝 Computer Science

인덱스(Index)

인덱스(Index) 데이터 레코드를 빠르게 접근하기 위해 쌍으로 구성되는 데이터 구조이다. 데이터 테이블을 Full Scan 하지 않고 인덱스를 이용해 검색해서 검색 속도 향상하고 디스크 연산 횟수를 줄인다. 검색 쿼리의 성능을 월등히 향상시키는 인덱스가 항상 좋지만은 않다. 인덱스를 생성하게 되면 삽입, 삭제, 갱신 등의 추가적인 과정이 발생하기 때문에 그만큼 성능 손실이 발생한다. 인덱스 엔트리: 인덱스 파일의 레코드이다. 데이터 레코드의 수보다 작거나 같다. 종류 밀집 인덱스: 데이터 파일 내 모든 키 값을 인덱스 엔트리로 정의한다. Ex) 클러스터드 인덱스 희소 인덱스: 탐색 값 일부에 대해서만 인덱스 엔트리를 정의한다. Ex) 기본 인덱스, 보조 인덱스 1) 클러스터드 인덱스 vs 넌클러스터드 ..

데이터베이스(DataBase)

파일 시스템과 데이터베이스 데이터베이스가 존재하기 이전에는 파일 시스템을 이용하여 데이터를 관리하였다. 1. 파일 시스템 파일 시스템은 파일을 이용하여 자료를 관리하는 방법으로 파일은 물리적인 비트의 연속이고 순차적인 레코드들로 구성된다. 여기서 레코드란 연관된 필드들의 모임을 말한다. 데이터에 대한 프로그램의 의존도가 높음(종속성): 프로그램 안에 데이터의 정의가 존재하기 때문에 데이터 구조를 수정하면 프로그램을 수정해야 한다. 데이터의 중복성으로 불일치 현상: 동일한 사실에 서로 다른 데이터가 존재해서 정보에 대한 혼란과 저장 공간 낭비가 발생한다. 부족한 기능 데이터 모델링 개념: 프로그래밍에 규칙이 없다. 질의어: 일일이 프로그래밍해야 한다. 동시성 제어: 여러 사용자가 동시에 액세스 하면 데이터..

해시(Hash)

해시(Hash) 적은 자원으로 데이터를 효율적으로 관리하기 위해 임의의 길이 데이터를 고정된 길이의 데이터로 매핑하는 것이다. 해시 함수를 사용하여 저장할 데이터와 연관된 고유한 숫자를 만든 뒤 이를 인덱스로 사용한다. 내부적으로 배열을 이용하여 데이터를 저장하기 때문에 빠른 검색 속도(O(1))를 갖는다. 1. 해시 함수(Hash Function) 저장할 데이터와 연관된 고유한 숫자(Hash Code)를 만든다. 저장되는 값들의 key 값을 해시 함수를 통해 작은 범위의 값들로 바꾼다. 2. 해시 테이블 해시 테이블은 원소가 저장될 자리가 원소의 값에 의해 결정되는 자료구조로 임의의 원소를 해시 테이블에 저장하려면 해시 함수를 통해 해시 값을 계산하고 해시 값에 따라 저장한다. 3. 충돌(Collisi..

그래프(Graph)

그래프(Graph) 정점(Vertex)과 간선(Edge)의 집합이다. 방향성(Directed) 그래프: 간선에 방향성이 포함된 그래프이다. 무방향성(Undirected) 그래프: 방향성이 없는 그래프이다. 가중치(Weight) 그래프: 간선에 가중치 정보가 포함된 그래프이다. 부분(Sub) 그래프: 그래프의 일부 정점 및 간선으로 이루어진 그래프이다. 1. 구현 방법 1) 인접 행렬 정점(V)의 수만큼 2차원 배열을 만들고 인접하면 1, 인접하지 않으면 0을 넣는 방법으로 메모리 낭비(V^2)가 있으나 밀도가 높은 그래프 표현에 적합하다. 2) 인접 리스트 각 정점마다 리스트를 만들고 인접해 있는 정점들을 연결한 방법으로 검색 시간이 오래 걸리지만 메모리 낭비가 없다. 2. 그래프 탐색 1) 깊이 우선 ..

이진 트리(Binary Tree)

이진 트리(Binary Tree) 어떤 노드의 자식 노드의 수가 최대 2개를 넘지 않는 트리이다. 포화(Perfect) 이진트리: 모든 레벨이 꽉 찬 이진트리이다. 완전(Complete) 이진트리: 위에서 아래로, 왼쪽에서 오른쪽으로 차례대로 채워진 트리이다. 사향 이진트리: 한쪽으로 기울어진 트리로 탐색 시간은 O(N)이다. 1. 이진 탐색 트리(Binary Search Tree) 탐색 시간이 평균 O(logN)으로 효율적인 탐색이 가능하다. 각 노드의 자식이 2개 이하이다. 각 노드의 왼쪽 자식은 부모보다 작고 오른쪽 자식은 부모보다 크다. 중복된 값의 노드가 없어야 한다. 2020.04.29 - [📝 Computer Science/✏ Algorithm] - [C] 이진 탐색 트리(BST) [C] 이..

선형 구조(Linear Structure)와 비선형 구조(Non-Linear Structure)

1. 선형 구조 데이터를 연속적으로 연결되어 있는 모양으로 구성한다. 1) 배열(Array) 동일한 자료형의 데이터들이 같은 크기로 나열되어 순서를 갖고 있는 집합이다. 빠른 접근(O(1))과 random access가 가능하다. 논리적 저장 순서와 물리적 저장 순서가 일치하기 때문에 인덱스로 해당 원소에 접근할 수 있다. 인덱스란 배열의 요소를 간단히 구별하기 위해 사용하는 번호이다. (0 ~ n-1) 정적인 자료 구조로 기억 장소의 추가가 어렵고 데이터 삭제 시 데이터가 저장되어 있던 기억 장소는 빈 공간으로 남아있어 메모리 낭비가 발생한다. 2) 배열 리스트(Array List) 배열과 같이 연속되는 기억 장소에 차례대로 데이터가 저장되지만 빈 공간이 없다. 기억 장소를 연속적으로 배정받기 때문에 ..