개발일지

블룸 필터개요　블룸 필터(Bloom filter)는 크기가 m인 비트 배열과 k개의 독립적인 해시 함수로 구성된 확률적 데이터 구조다. 컨테이너다. 초기에 모든 비트가 0으로 설정되어 있으며, 원소를 추가할 때마다 각 해시 함수를 사용하여 계산된 인덱스에 해당하는 비트를 1로 설정하는 방식으로 작동한다. 해시 테이블과 비슷하지만, 공간 효율이 매우 높다. 특징　블룸 필터의 가장 큰 특징은 공간 효율성이다. 원소를 직접 저장하지 않고 비트 배열을 사용해 원소의 존재 여부를 추적함으로써 메모리를 효율적으로 사용한다. 그러나, 비트를 이용한 데이터를 처리하는 방식으로 인해 거짓 - 양성이라는 부정확한 결과를 얻을 수 있다. 여기서 거짓 - 양성(false positive)이란 원소가 실제로 필터에 없지만 존재..

"; Insert(oldkey, count + 1, 2); } } else { int value = hash2(key); if (_table2[value] == -1) { std::cout

충돌 해결체이닝(Chaining)　해시 충돌 문제를 해결하는 첫 번째 방법인 체이닝 기법에서는 충돌이 발생한 지점에서 연결 리스트를 만든다. 즉, 이 방법은 해시 테이블의 특정 위치에서 하나의 연결 리스트를 저장하여, 충돌이 발생하면 리스트의 맨 뒤에 새로운 키를 추가하는 방식이다.  　연결 리스트는 포인터를 이용하여 다음 노드를 가리키기 때문에, 메모리를 재사용하지 않아 중간에 요소를 삽입하거나 삭제하는 경우에도 O(1) 시간에 수행할 수 있다는 장점이 있다. 그리고 배열과 다르게 데이터가 흩어져 있지 않고 연속된 메모리 공간을 차지하지 않으므로, 캐시 효율성이 높다. 　이러한 체이닝 기법을 이용하여 이전 충돌 문제를 해결해 보자. #include #include #include #include cla..

해시 테이블(Hash Table)개요　해시 테이블은 키(key)와 값(value)을 이용해 데이터를 저장하는 자료구조로서, 키를 주어진 데이터로부터 고유한 숫자 값을 계산하는 해시 함수(hash function)를 이용해 해시 값으로 변환한 후, 해당 해시 값에 해당하는 위치에 값을 저장한다. 여기서 해시 값(hash value)이란 해시 함수에 의해 반환되는 숫자를 의미한다. 　키와 값을 이용한 자료구조라는 점에서 std::map 자료구조와 비슷하다고 생각할 수 있다. 실제로 두 컨테이너는 유사하지만, 내부 구조와 동작 방식, 그리고 성능 특성 등에서 차이가 있다.   hash tablemap탐색이진 탐색해싱정렬XO속도O(1)O(logN)해싱과 충돌　해시 테이블의 핵심은 해싱이다. 해싱(hashing)..

그래프(Graph)개요　지금까지 공부한 트리는 계층적인 데이터를 표현하기에 적합한 자료구조지만, 원형 또는 순환적인 종속성을 표현할 수 없다. 예를 들어 서울과 광역시간의 이동 정보를 생각해 보면, 특정 장소에서 다른 장소로 이동하기 위한 다양한 경로가 존재할 수 있다. 이러한 경우엔 노드와 간선(edge)을 모아놓은 자료구조인 그래프를 사용하는 것이 더 적합하다. 그래프는 순환 구조를 가지므로, 이러한 경우에도 경로를 표현할 수 있다. 따라서, 계층적인 데이터가 아닌 경우엔 그래프를 사용하는 것이 더욱 유용할 것이다.종류　그래`프는 다양한 종류가 있으며, 먼저 무방향(Undirected) 그래프와 방향(Directed) 그래프로 나뉜다. 무방향 그래프에서는 간선이 양방향으로 연결되어 있으며, 방향 그래..

힙(Heap)개요　우리는 힙 자료구조에 대해 이전에 컨테이너 어댑터 포스팅에서 간략하게 알아본 적이 있다. 특정한 우선순위를 갖는 이 컨테이너에 대해 더욱 자세하게 알아보는 시간을 갖도록 하자. 　힙은 다음과 같은 시간 복잡도 특징을 갖고 있다.최대/최소 원소에 접근: O(1)원소 삽입, 삭제: O(logN) 　힙은 다음과 같은 특징이 있다.부모 노드와 자식 노드의 우선순위는 항상 유지우선순위가 높은 원소는 항상 루트 노드에 존재완전 이진 트리(Perfect Binary Tree)　힙은 원소 삽입 또는 삭제에 대해 O(logN)의 시간 복잡도를 만족해야 하기 때문에 일반적으로 완전 이진트리를 사용해야 한다. 여기서 완전 이진 트리(Complete Binary Tree, 포화 이진트리)는 레벨 순서대로 왼..

구현　위의 검색 / 삽입 / 삭제의 특성을 가지는 BST를 구현하는 시간을 가지도록 하자. #include using namespace std;struct Node{ int _data; Node* _left, * _right;};　트리에 사용될 노드 구조체 Node를 선언한다. class BST{ Node* _root;public: BST() : _root(nullptr) {}　이진 탐색 트리 클래스 BST를 선언하고, 기본 생성자를 통해 루트 노드를 nullptr로 초기화해 준다. class BST{ ... Node* Find_Implementation(Node* node, int value) { if (!node) // node가 존재하지 않는 경우 return NULL; if (node->_..

이진 검색 트리 (BST)개요　이진 검색 트리(Binary Search Tree - BST)는 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 이진트리의 일종으로서, 특정한 규칙을 통해 검색을 하는 자료구조다. 각 노드는 하나의 값을 가지며, 다음과 같은 특징이 있다.왼쪽 노드의 값 ≤ 부모 노드의 값 ≤ 오른쪽 노드의 값중복된 값을 갖는 노드가 존재하지 않음이진 탐색 트리의 모든 서브 트리도 이진 탐색 트리따라서 BST는 부모 노드보다 작거나 같은 모든 원소는 항상 왼쪽에 있고, 부모 노드보다 크거나 같은 원소는 항상 오른쪽에 있다. 이를 그림으로 나타내면 다음과 같다. 　  　이러한 BST는 이름에 걸맞게 탐색 속도가 빠르다. BST는 높이에 따라 시간 복잡도가 결정되며, 이를 O(높이)로 표현할..

트리 순회개요　앞선 포스팅에선 트리에 원소를 삽입하는 방법에 대해 알아보았다. 이번 포스팅에선 트리의 원소를 순회하는 방법에 대해 알아보도록 하자. 여기서 순회란 모든 노드를 한 번씩 방문하는 것을 의미한다.본문　트리를 순회하는 방법은 크게 4가지가 존재한다.전위 순회(Preorder traversal): 현재 노드를 먼저 방문하고, 그다음은 현재 노드의 왼쪽 하위 노드, 마지막으로 현재 노드의 오른쪽 하위 노드를 재귀적으로 방문하는 방식.중위 순회(In-order traversal): 왼쪽 노드를 먼저 방문하고, 그다음에는 현재 노드, 마지막으로 오른쪽 노드를 방문하는 방식.후위 순회(Post-order traversal): 두 자식 노드를 먼저 방문한 후, 현재 노드를 방문하는 방식.레벨 순서 순회(..

트리(Tree)  개요　지금까지 다룬 자료 구조는 순방향과 역방향을 지원하는 선형 자료 구조였다. 이러한 구조는 특정 데이터를 검색할 때 순서대로 자료를 찾아나가야 하는 문제점과, 데이터를 저장하기 위해 일정한 공간을 미리 할당해야 하는 등 제한적인 구조를 갖고 있어 복잡한 문제를 해결하는 데 어려움이 있다. 대표적인 문제로는 계층적 문제와 순환 종속성 문제가 있다. 　계층적 문제(Hieararchy Problem)란 계층적 속성을 갖는 자료를 선형 구조로 표현하기 어렵다는 것을 의미한다. 다음과 같은 조직도를 표현한다고 해보자.  　이러한 조직을 표현하기 위해서, 기존에 배운 선형 자료 구조인 배열과 벡터, 리스트를 이용해 표현하기는 어려워 보인다. 　순환 종속성(Cyclic Dependency) 문제..