Computer Science/Data Structure7

• 

  레드-블랙 트리 (Red-Black Tree) 레드-블랙 트리(Red-Black Tree, RB Tree) 트리(Tree)의 가장 큰 장점은 분기(branch)마다 데이터 탐색 범위를 대폭 줄여나간다는 것이다. 하지만 이 장점을 제대로 활용하기 위해서는 트리 자체가 균형을 이뤄야 한다. 즉, 편향된 트리는 메모리만 더 많이 사용할 뿐 $O(N)$ 속도로 탐색되기 때문이다. 이러한 문제점을 해결하기 위해 B Trees와 같이 자가 균형 트리(Self-Balanced Tree)들이 등장했다. 레드-블랙 트리(RB Tree)는 자가 균형 이진 탐색 트리(Self-Balanced Binary Search Tree)로 1978년 레오 귀바스(Leo J. Guibas)와 로버트 세지윅이 1972년 루돌프 바이어가 창안한 "대칭형 이진 B-트리"를 발전시켜 만들.. Computer Science/Data Structure 2022. 6. 5.

• 

  B Trees (B-Tree & B+ Tree & B* Tree) B Trees B Trees는 데이터 탐색을 더 빠르게 하기 위한 자체 균형 트리(Self-Balanced Tree) 중 하나이다. 트리 종류 중 편향 트리(Skewed Tree)는 최악의 경우 시간 복잡도가 O(N)으로 늘어난다. 따라서, 트리는 편향되지 않도록 균형을 맞추면서 데이터를 저장하는 것이 중요하다. 균형 트리들은 각 트리마다 균형을 맞추는 방법이 조금씩 다르다. B Trees는 주로 디스크를 이용하는 파일 시스템(File System)이나 데이터베이스(RDBMS)에서 인덱스를 통한 빠른 데이터 조회를 위해 사용되는 자료구조이다. 데이터를 빨리 찾기위해 인덱스를 작성하기 시작했으며, 데이터가 많아지자 인덱스 양도 늘어나게 됐다. 인덱스의 효용성을 늘리기 위해 인덱스의 인덱스가 작성됨에 따라 .. Computer Science/Data Structure 2022. 6. 2.

• 

  해시 테이블(Hash Table) 해시 테이블(Hash Table) 해시 테이블(Hash Table)이란 Key-Value 쌍으로 데이터를 저장하는 자료구조이다. 배열에서 인덱스를 통해 값에 접근하듯이, 해시 테이블 역시 Key를 통해 Value에 접근한다. 배열의 인덱스는 중복되지 않는 정수이지만, 해시 테이블의 Key는 다양한 자료형이 올 수 있다. 하지만 기본적인 저장공간은 배열이기 때문에 결국 Key를 정수인 Index로 변환해야 한다. 이 변환해주는 함수를 해시 함수(Hash Function)라고 한다. 즉, Key를 해시함수 H를 통해 H(key)라는 인덱스를 만들고, 이를 통해 배열에 저장된 Value를 획득하는 방법이다. 해시값을 통해 접근하는 배열을 버킷(Bucket)이라고 한다. 결국 Key를 해시 함수에 한 번만 적용.. Computer Science/Data Structure 2022. 6. 1.

• 

  그래프(Graph) 그래프(Graph) 그래프(Graph)는 노드/정점(Node, Vertex)와 간선(Edge)로 구성된 비선형 자료구조를 의미한다. 트리와 다르게 정점과 정점 사이의 간선이 여러 개 있을 수 있고, 순환(Cycle)이나 자체 순환(Self-Loop)도 가능하다. 그래프는 간선에 가중치(Weight)가 부여되는 경우가 많다. 트리는 그래프의 부분 집합이다. 그래프와 트리 차이 용어 정점(vertex): 위치라는 개념. (node 라고도 부름) 간선(edge): 위치 간의 관계. 즉, 노드를 연결하는 선 (link, branch 라고도 부름) 인접 정점(adjacent vertex): 간선에 의 해 직접 연결된 정점 정점의 차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수 무방향 그래프.. Computer Science/Data Structure 2022. 5. 31.

• 

  트리(Tree) & 이진탐색트리(BST) & 힙(Heap) 트리 트리(Tree)란 그래프(Graph)의 일종으로, 여러 노드가 한노드를 가리킬 수 없는 구조이다. 즉, 회로(Cycle)가 없고, 서로 다른 두 노드를 잇는 길이 하나뿐인 그래프를 트리라고 부른다. 데이터를 순차적으로 저장하지 않으므로 비선형 자료구조다. 연결된 무방향 그래프 구조이다. 용어 용어가 많아 시간이 지나면 헷갈릴 수 있다. 루트 노드(root node): 부모가 없는 노드, 트리는 하나의 루트 노드만을 가진다. 단말 노드(leaf node, terminal node, external node): 자식이 없는 노드, ‘외부 노드’ 또는 ‘잎 노드’라고도 부른다. 내부 노드(internal node, non-terminal node, branch node): 단말 노드가 아닌 노드, '가지.. Computer Science/Data Structure 2022. 5. 30.

• 

  스택(Stack) & 큐(Queue) & 덱(Deque) 스택(Stack) 스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO - Last In First Out)으로 되어 있다. 자료를 넣는 것을 '밀어넣는다' 하여 푸쉬(push)라고 하고 반대로 넣어둔 자료를 꺼내는 것을 팝(pop)이라고 하는데, 이때 꺼내지는 자료는 가장 최근에 푸쉬한 자료부터 나오게 된다. 이처럼 나중에 넣은 값이 먼저 나오는 것을 LIFO 구조라고 한다. 스택은 컴퓨터에서 포인터라고 하는 자료의 위치 표시자와 넣고 빼는 명령어를 사용해서 스택을 이용한다. 주로 함수를 호출할 때 인수의 전달 등에 이용되며 대표적인 예시는 아래와 같다. 웹 브라우저 방문 기록 후위 표기법 계산 실행 취소(Undo) 역순 문자열 생성 Java에서 Stack은 Vector를 상속하여 만들.. Computer Science/Data Structure 2022. 5. 27.

• 

  배열(Array) & 배열 리스트(ArrayList) & 연결 리스트(LinkedList) & 벡터(Vector) 배열(Array) 배열은 번호(인덱스)와 번호에 대응하는 데이터들로 이루어진 자료 구조를 나타낸다. 일반적으로 배열에는 같은 종류의 데이터들이 순차적으로 저장되어, 인덱스가 곧 배열의 시작점으로부터 값이 저장되어 있는 상대적인 위치가 된다. 대부분의 프로그래밍 언어에서 사용할 수 있는 가장 기초적인 자료 구조로, 기본적인 용도 외에 다른 복잡한 자료 구조들을 표현하기 위해서 또는 행렬, 벡터 등을 컴퓨터에서 표현하는 용도 등으로도 사용된다. 배열의 첫 번째 요소의 메모리 주소를 첫 번째 주소, 기본 주소 또는 기본 주소라고 한다. 장점 인덱스를 통해 접근하기 때문에 시간 복잡도가 O(1)이다. 데이터의 크기가 고정적일 때, 배열을 이용하면 메모리 사용량이나, 처리 속도면에서 좋다. 구현이 쉽다. 단점 크.. Computer Science/Data Structure 2022. 5. 25.