CS/Data Structure

Trie(트라이)? 트라이는 문자열을 저장하고 효율적으로 탐색하기 위한 트리형태의 자료구조이다. 우리가 검색할 때 볼 수 있는 자동완성 기능, 사전 검색 등 문자열을 탐색하는데 특화되어있는 자료구조라고 한다. 래딕스 트리(radix tree), 접두사 트리(prefix tree)혹은 탐색 트리(retrieval tree)라고도 한다. 트라이는 retrieval tree에서 나온 단어이다. 예) Datastructure라는 단어를 검색하기 위해서는 제일 먼저 'D'를 찾고, 다음에 'a', 't', ... 의 순서로 찾으면 된다. 이러한 개념을 적용한 것이 트라이(Trie)이다. 정수형에서 이진탐색트리를 이용하면 시간복잡도 O(logN) 하지만 문자열에서 적용했을 때, 문자열 최대 길이가 M이면 O(M*l..

Hash(해시)? 해시는 입력된 데이터를 고정된 길이의 데이터로 변환 값을 말한다. 데이터를 효율적으로 관리하기 위해, 임의의 길이 데이터를 고정된 길이의 데이터로 매핑하는 것 해시 함수를 구현하여 데이터 값을 해시 값으로 매핑한다. 데이터가 많아지면, 다른 데이터가 같은 해시 값으로 충돌나는 현상이 발생함 collision 현상 정수로 변환된 해시는 배열의 인덱스, 위치, 데이터 값을 저장하는데 활용된다. 언제나 동일한 해시값 리턴하고, index를 알면 빠른 데이터 검색이 가능해진다. 해시테이블의 시간복잡도 O(1) 이진탐색트리는 O(logN) 해시 함수(Hash Function) 임의의 데이터를 고정된 길이의 값으로 리턴해주는 함수 해시 함수는 입력 받은 데이터를 해시 값으로 출력시키는 알고리즘을 ..

B-Tree? 이진 트리는 하나의 부모가 두 개의 자식밖에 가지질 못하며, 균형이 맞지 않으면 검색 효율이 선형 검색 급으로 떨어진다. 단, 이진 트리의 구조의 간결함과 균형만 맞다면 검색, 삽입, 삭제 모두 O(log N)의 성능을 보이는 장점이 있다. 이러한 장점 때문에 계속해서 개선하고자하는 노력이 이루어지고 있다. B-Tree는 이진 트리를 확장해서 더 많은 자식을 가질 수 있도록 일반화하였다. B Tree는 자식 수를 일반화 하면서 하나의 레벨에 더 많이 저장된다. 또한 트리의 균형을 자동으로 맞추는 로직까지 갖추었다. 균형을 맞추는 로직은 간단하면서 효율적이다. B Tree는 레벨로만 따지면 완전히 균형을 맞춘 트리이다. 데이터베이스와 파일 시스템에서 널리 사용되는 트리 자료구조의 일종이다. ..

Binary Search Tree(이진 탐색 트리)? 왼쪽 자식은 부모보다 작고 오른쪽 자식은 부모보다 큰 이진 트리이다. BST는 아래와 같은 조건을 가진다. 부모 노드의 왼쪽 노드는 부모 노드보다 작아야 한다. 부모 노드의 오른쪽 노드는 부모 노드보다 커야 한다. BST는 삽입, 삭제, 탐색과정에서 모두 트리의 높이만큼 탐색하기 때문에 O(logN)의 시간 복잡도를 가진다. 트리가 편향트리가 되어버렸을 때 결국 배열과 다름 없어지고 시간 복잡도는 O(N)이 된다. 중복된 노드가 존재하지 않는다. 검색 목적 자료구조인데, 굳이 중복이 많은 경우에 트리를 사용하여 검색 속도를 느리게 할 필요가 없음 트리에 삽입하는 것보다, 노드에 count 값을 가지게 하여 처리하는 것이 훨씬 효율적 이진탐색트리의 순회..

Tree(트리)? 트리는 값을 가진 노드(Node)와 이 노드들을 연결해주는 간선(Edge)으로 이루어진 자료구조이다. 트리는 하나의 루트(Root) 노드를 가진다. 루트 노드는 0개 이상의 자식 노드를 가진다. 그 자식 노드 또한 0개 이상의 자식 노드를 갖고 있고, 이는 반복적으로 정의된다. 트리의 모든 노드들은 0개 이상의 자식 노드를 갖고 있으며, 보통 부모-자식 관계로 부른다. 가족 관계도를 트리 형식으로 나타내며, 자료구조인 트리도 이 방식을 그대로 구현한 것 그래프 vs 트리 그래프와 트리의 차이점은 사이클(Cycle)의 유무로 설명할 수 있다. 사이클이 존재하지 않는 그래프라고 하여 무조건 트리인 것은 아니다. 사이클이 없는 그래프는 Forest라고 지칭한다. 트리의 경우 사이클이 없고 모..

Heap(힙)? 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree) 힙은, 우선순위 큐를 위해 만들어진 자료구조다. 우선순위 큐란 우선순위 개념을 큐에 도입한 자료구조이다. 데이터들이 우선순위를 가지고 있어 우선순위가 높은 데이터가 먼저 나가게 된다. 반정렬 상태를 유지 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도 간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리를 말한다. 힙 트리는 중복된 값을 허용 이진 탐색 트리는 중복 값을 허용하지 않음 완전 이진 트리? 이진 트리에 노드를 삽입할 때 왼쪽부터 차례대로 삽입하는 트리이다. 왼쪽이 비어있고 오른쪽이 채워져 있는 형태는 완전 이진 트리라고 할..

Queue(큐)? 큐 자료구조는 스택과 다르게 선입선출(FIFO)의 구조를 가지고 있다. queue는 사전적으로 대기줄을 뜻한다. 입력과 출력을 한 쪽 끝(front, rear)으로 제한한다. Queue의 활용 버퍼 마구 입력된 것을 처리하지 못하고 있는 상황 BFS 데크(Deque), 우선순위 큐(Priority Queue) 등으로 변형 캐시 구현 어떠한 작업/데이터를 순서대로 실행/사용하기 위해 대기 Queue의 연산자 큐의 가장 첫 원소를 front, 끝 원소를 rear라고 부름 큐는 들어올 때 rear로 들어오지만, 나올 때는 front부터 빠지는 특성을 가짐 접근방법은 가장 첫 원소와 끝 원소로만 가능 enQueue() 데이터 넣음 deQueue() 데이터 뺌 isEmpty() 비어있는 지 확인..

스택이란? 스택은 컴퓨터에서 아주 많이 사용되는 자료구조이다. 휴대폰의 뒤로 가기 기능은 스택을 사용하여 현재 실행되는 앱을 종료하고 이전에 실행되던 앱을 실행한다. 스택(Stack)은 쌓아놓은 더미를 뜻한다. 스택의 가장 큰 특징은 후입선출(LIFO)이다. 가장 가중에 들어온 것이 가장 먼저 나온다. 입력과 출력이 한 방향으로 제한된다는 특징이 있다. 스택의 구조 스택은 자료의 출력 순서가 입력 순서의 역순으로 이루어질 때 사용되는 자료구조이다. 스택 상단(Stack Top) : 스택에서 입출력이 이루어지는 부분 스택 하단(Stack Bottom) : 스택의 바닥 부분 요소(Element) : 스택 자료구조에 저장된 데이터 시스템 스택 함수호출 시스템 스택(System Stack) 운영체제가 사용하는 ..