자료구조

Hash Table

Hash Table 해시 테이블은 무한에 가까운 데이터들을 유한한 개수의 해시 값으로 매핑한 테이블이다. 따라서 작은 크기의 캐시 메모리로도 프로세스를 관리하도록 할 수 있다. 삽입, 삭제, 탐색 시 평균적으로 O(1)의 시간 복잡도를 가지고 unordered_map으로 구현한다. 해시 테이블에 데이터를 삽입하기 위해서는 저장하고자 하는 자료와 연관된 키를 생성해야 하는데 이 키를 생성하기 위한 함수를 해시 함수라고 한다. 좋은 해시 함수를 사용하면 해시 테이블에 데이터가 고르게 분포되고, 이는 충돌이 발생할 가능성이 낮다는 뜻이다. 따라서 좋은 해시 함수는 충돌을 덜 일으켜야 하고 계산이 쉬워야 한다. Hash Collision 서로 다른 두 개의 값 $i_{1}$과 $i_{2}$가 해시 테이블의 같은..

Red-Black Tree(RBT)

Red-Black Tree 레드 블랙 트리는 균형 이진 탐색 트리로 탐색, 삽입, 삭제 모두 시간 복잡도가 logN이다. 각 노드는 빨간색 또는 검은색의 색상을 나타내는 추가 비트를 저장하고, 추가된 비트는 삽입 또는 삭제의 과정에서 트리가 균형을 유지하도록 하는 데 사용된다. 대표적으로 C++ STL의 set, multiset, map, multimap 이 레드 블랙 트리를 이용하여 구현되어있다. Why Red-Black Tree? 왜 레드 블랙 트리를 사용하는 걸까? 이 이유에 대해 알기 위해서는 BST(이진 탐색 트리)의 단점부터 파악해야 한다. BST란, 노드의 오른쪽 하위 트리에는 노드 값보다 큰 값이 있는 노드만 포함되고, 왼쪽 하위 트리에는 노드 값보다 작은 값이 들어 있는 트리를 말한다. ..

Heap(Max Heap, Min Heap)

Heap 영단어 Heap은 '무엇인가를 차곡차곡 쌓아 올린 더미'라는 뜻을 가지고 있다. 아래 그림에서도 볼 수 있듯이, 맨 아래부터 데이터를 차곡차곡 쌓아둔 모양이다. Heap은 완전 이진트리로 모든 노드가 연속적으로 존재하기 때문에 연결 리스트보다는 배열로 구현하는 것이 효율적이다. 또한 heap은 모든 노드에 저장된 값이 자식 노드에 저장된 값보다 크거나 같은 자료구조이다. 즉, 루트 노드에 저장된 값이 가장 커야 한다. 이처럼 루트 노드로 올라갈수록 저장된 값이 커지는 완전 이진트리를 최대 힙(Max Heap)이라고 한다. 이와 반대로, 루트 노드로 올라갈수록 저장된 값이 작아지는 완전 이진 트리인 최소 힙(Min Heap)도 존재한다. 최소 힙은 특히 shortest job first를 구현할때..