해시 테이블 이번글은 뻐꾸기 해싱(Cuckoo Hashing)에 대한 글입니다! 해시 테이블의 핵심은 '해싱'입니다. '해싱'이란 각각의 주어진 데이터를 최대한 고유한 숫자 값으로 표현하여 나중에 해당 데이터의 유무를 확인하거나 해당 데이터에 대응하는 원본 데이터를 추출 하는 작업입니다. 그리고 주어진 데이터로 부터 고유한 숫자 값을 계산하는 함수를 '해시 함수'라고합니다. 그래서 해시 함수를 무엇을 정하느냐에 따라 해시 함수를 통해 나오는 '해시 값'이 각기 달라지겠지만 가장 일반적인 방법으로는 입력 받은 데이터 : x 가 있을 때 (x % n)으로 '해시 값'을 반환합니다. 이런 방법으로 해시 맵을 구성하여 데이터를 넣다보면 n이 7이라 가정을 했을 때 x가 3, 10 순으로 들어오게 된다면 (x %..

이전에 힙을 구현한적이 있는데 다시 정리해서 구현한 글입니다. 힙? 힙이란? '이진트리'이면서 '완전 이진트리'입니다. 힙은 max heap, min heap으로 나뉩니다. 중요한 점은 heap은 '완전 이진트리'라는 점입니다. 이진트리는 자식의 최대 개수가 두개인 트리의 형태를 의미합니다. 완전 이진트리는 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있는 이진트리입니다. 트리에 대한 개념은 https://code-lab1.tistory.com/8

AVL 트리란? 이번글은 https://cjbworld.tistory.com/25 의 코드에 기반을 두고 확장하여 작성한 버젼입니다. 기존의 이진 탐색트리에서 탐색의 경우 "로그 시간복잡도를 보장해준다"라고 알고있는데 예외가 존재합니다. 바로 BST애 데이터를 삽입할 때 데이터들을 오름차순으로 삽입할 경우 트리의 모양이 요런식으로 되어 버려 탐색시 로그 시간복잡도가 안나온다는 것입니다... 선형시간 복잡도가 나오겠지용 그래서 이러한 문제점을 해결해주는 도구들이 바로 AVL 트리, 2-3-4트리, B트리, 2-3트리, Red-Black트리 등등이 있습니다. 이중에서도 AVL트리에 대해서 다뤄볼 것인데요. 이 AVL트리에는 위의 그림판 그림처럼 "균형"이 안맞는 상황을 위해 몇가지 개념이 추가가 됩니다. 바..

Heap? 힙이라는 자료구조를 알아보기 전에 먼저 "우선순위 큐"가 무엇인지 잠시 살펴보겠습니다. PQ(우선순위 큐)는 "들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는" 특징을 가지고 있습니다. 즉, PQ는 데이터를 근거로 우선순위를 "판단"할 수 있어야 한다는 말입니다. 이 PQ를 구현을 할때 - 배열을 통해 구현 - 연결형 리스트를 통해 구현 - heap을 통해 구현 이렇게 세가지 정도로 볼 수 있습니다. 배열이나 연결형 리스트를 사용하면 PQ를 매우 간단히 구현할 수 있습니다. 하지만 이들은 PQ를 구현하는데에 있어서 그리 적합하지 않은데요 이유를 설명해드리도록 하겠습니다. 우선 "배열"의 경우 데이터의 우선순위가 높을 수록 배열의 앞부분에 데이터를 위치시킬 수 있습니다. 하지만 st..

간단한 사칙연산 계산기 구현입니다. C, C++을 통해서 계산기를 구현한 코드입니다. 먼저 알아야할 개념은 두가지 입니다. 1. 자료구조 스택 (LIFO) 2. 수의 중위 표기법, 전위 표기법, 후위 표기법 중위 표기법은 1+2*3 과같은 저희가 사용하는 수식입니다. 전위 표기법은 +1*23 후위표기법은 123*+ 입니다. 순서는 "Stack 자료구조 구현 => 중위 표현식을 후위 표현식으로 변경 => 후위 표현식을 계산" 입니다. 스택의 중위 => 후위로 변경할 때 사용하는 자료구조 입니다. 연산자의 우선순위가 높다면 스택에 쌓아두고 그렇지 않다면 현재 스택에서 pop() 을 진행한뒤 쌓아둡니다. 후위 표기법의 계산은 12+3*순일경우 앞에 있는 수 12를 차례대로 끄집어 낸다음 뒤에오는 '+' 연산자..

이번글은 간단한 Iterator의 종류와 구분방식을 살펴보고 정리한 뒤 advance, distance를 직접 구현한 글입니다 :) (STL 기본 컨테이너의 동작방식이나 개념은 없습니당) STL의 vector, deque, list는 sequence container로 원소의 위치가 정해진 상태로 삽입됩니다. STL의 set, multiset, map, multimap의 경우 associate containder로 원소의 삽입 위치가 특정 조건에 따라 달라집니다.(default는 less() 입니다) 또한 시퀀스 컨테이너는 선형적이며, 연관 컨테이너는 비선형적 이라고 구분할 수 있습니다. 그중에서도 STL의 vetor, deque가 배열기반의 컨테이너이며(데이터 여러개가 하나의 메모리 단위에 저장) li..

#include #include using namespace std; template class Vector { private: T*addr; int dataSize; int dataMaxSize; public: Vector() : addr(nullptr), dataSize(0), dataMaxSize(2) { addr = new T[dataMaxSize]; } virtual ~Vector() { delete[] addr; } public: void push_back(const T& value); void resize(const int& resize); T& data() const { return addr; } const int& size() const { return dataSize; } const i..