CS/자료구조

[자료구조/C++] 해시 테이블(hash table)과 체이닝(chaining) - vector와 list로 구현

[ 1 ] 해시 테이블(hash table)이 필요한 이유 옥스포드 영어 사전에는 약 170,000개의 단어가 수록되어 있다고 한다. 이 사전에서 하나의 단어를 탐색하는데 시간 복잡도가 O(n)인 선형 탐색을 활용한다면 오랜 시간이 걸릴 것이다. 이를 해결하기 위해 AVL Tree나 Red-Black Tree처럼 트리의 높이를 O(log n)으로 유지하는 자료구조를 활용한다면 선형 탐색보다 그 검색 시간을 유의미하게 줄일 수 있을 것이다. 하지만, 데이터의 수가 증가하거나 탐색 횟수가 크게 증가할 경우 O(log n)의 속도도 만족스럽지 못할 수도 있기 때문에 우리는 더욱 효율적인 데이터 저장 - 탐색을 위한 자료구조를 떠올려야 한다. 이때 해시 테이블(hash table)이 효율적이고 효과적인 자료구조..

[자료구조/C++] 맵(map)

[ 1 ] 기본내용 map은 기본적으로 entry라고 불리는 (key, value)쌍이 저장되는 자료구조이다. 하나의 map은 중복된 key값을 가질 수 없다는 특성과 key값으로 해당 key값과 mapping된 value를 쉽게 검색할 수 있는 특성으로 인해 정보 저장 및 검색에 유리한 자료구조이다. 대표적인 map의 특성은 다음과 같다. - map은 중복된 key값을 가질 수 없기 때문에 하나의 key가 여러 개의 value값을 가질 수 없다. - map의 주요 연산으로는 search, insert, erase가 있다. - map을 연결리스트로 구현할 경우 위의 주요 연산의 시간복잡도는 O(n)이다. - map 연산의 시간복잡도를 줄이기 위해 hash map 등을 활용하기도 한다. [ 2 ] C++에..

[자료구조/C++] 이진탐색트리 (Binary Search Tree)

[ 1 ] 트리란? 트리는 대표적인 비선형 자료구조이며 노드와 노드를 연결하는 에지를 통해 계층을 구성한다. 이때 트리의 중심이 되는 노드를 root라고 하며, 이 노드는 일반적으로 맨 위에 나타난다. 즉, 트리 구조를 그림으로 나타낼 때는 실제 나무와는 반대로 뿌리가 맨 위에 나타나게 되는 것이다. 트리를 통해 우리는 선형 자료구조로는 표현할 수 없는 계층적 문제를 표현할 수 있다. [ 2 ] 이진탐색트리 (Binary Search Tree) [ 2 - 1 ] 이진트리 이러한 트리 중에서도 각 노드가 최대 2개의 자식 노드만 가질 수 있는 '이진 트리'가 자주 활용되는데, 이진 트리에도 Complete Binary Tree, Full Binary Tree, Binary Search Tree, AVL T..

[자료구조/C++] 우선순위 큐

[ 1 ] 기본내용 우선순위 큐(Priority Queue)란 First-In First-Out(FIFO) 구조를 따르는 일반적인 큐와 달리 힙(heap)을 활용하여 원소들의 우선순위를 설정하고, 우선순위에 따라 가장 작은(또는 가장 큰) 원소에 빠르게 접근할 수 있는 자료구조이다. 단, 최대 or 최소 둘 중 하나에 대해서만 우선순위를 적용할 수 있으며 최댓값을 우선순위로 둘 경우 최대 힙(Max heap), 최솟값을 우선순위로 둘 경우 최소 힙(Min heap)이라 한다. [ 2 ] C++에서의 우선순위 큐 [ 2 -1 ] 헤더파일 C++에서는 container adaptor로서 priority_queue를 제공하고 있으며, vector를 기본 컨테이너로 사용한다. priority_queue를 사용하..