Brute force Study

블룸 필터(bloom filter)블룸 필터는 해시 테이블에 비해 공간 효율이 매우 높은 방법이지만, 결정적(deterministic) 솔루션 대신 부정확한 결과를 얻을 수 있다.거짓-부정(false-negative)dl 이 없다는 것은 보장하지만, 거짓-긍정(false-positive)는 나올 수 있다.즉, 특정 원소가 존재한다는 긍정적인 답변을 받을 경우, 이 원소는 실제로 있을 수도 있고 없을 수도 있다.그러나 특정 원소가 존재하지 않는다는 부정적인 답변을 받았다면 이 원소는 확실히 없다뻐꾸기 해싱과 마찬가지로 블룸 필터도 여러 개의 해시 함수를 사용한다정확도를 위해 세 개 이상을 사용해야 한다블룸 필터는 실제 값을 저장하지는 않으며, 대신 특정 값이 있는지 없는지를 나타내는 부울 타입 배열을 사용..

C++ 해시 테이블해시 구현에서 항상 양의 정수만 취급할 수는 없다.오히려 문자열 데이터를 다루게 되는 경우가 더 많다영어 사전을 구현하려면 영어 단어를 키로 사용하고, 뜻을 값으로 사용해야 한다모듈로 함수는 문자열에는 적용할 수 없다간단한 해결책은 문자열의 모든 문자에 대한 ASCII 코드 값을 모두 더한 후에 모듈로 연산을 하는 것이다.위 방법은 충돌이 빈번하게 발생할 수 있다C++은 문자열로부터 해시 값을 생성하는 용도로 std::hash>(std::string) 함수 객체를 제공한다이 함수 객체 내부에는 해시 함수 알고리즘이 구현되어 있다.C++은 문자열 이외에도 모든 기본 데이터 타입에 대한 해시 값을 생성하는 기능도 제공한다"체이닝을 사용하는 해시 테이블"에서 구현했던 해시 테이블 코드를 템플..

해시 테이블에서 충돌다수의 키를 저장할 수 없는 문제를 해결해보자체이닝앞에서는 하나의 해시 값에 대해 하나의 원소만을 저장했다.따라서 특정 해시 값 위치에 이미 원소가 존재한다면 새로운 값과 예전 값 중 하나를 버릴 수밖에 없었다.체이닝(chaining)은 두 값을 모두 저장할 수 있는 여러 방법 중 하나이다이 방법은 해시 테이블의 특정 위치에서 하나의 키를 저장하는 것이 아니라, 하나의 연결 리스트를 저장한다새로 삽입된 키에 의해 충돌이 발생하면, 리스트의 맨 뒤에 새로운 키를 추가한다따라서 다수의 원소를 원하는 만큼 저장할 수 있다벡터 대신 연결 리스트를 사용하는 이유는, 특정 위치의 원소를 빠르게 삭제하기 위함이다Example) 체이닝을 사용하는 해시 테이블#include #include #incl..

해시 테이블lookup(룩업, 조회)는 특정 원소가 컨테이너에 있는지 확인하거나 또는 컨테이너에서 특정 키(key)에 해당하는 값(value)를 찾는 작업을 의미한다DB에서 원하는 자료를 찾거나, 사전에서 단어의 뜻을 찾는 문제들이 이에 해당모든 원소를 선형으로 검토하여 원하는 값을 찾는 작업은 일반적으로 매우 많은 시간이 소요된다O(N) 시간 복잡도를 가짐이 작업을 훨씬 빠르게 수행할 수 있는 효과적인 알고리즘이 필요하다.해시 테이블과 블룸 필터라는 효과적인 구조에 대해 살펴본다.해시 테이블O(N)을 갖는 선형 검색보다 더 나은 검색 방법은 BST와 같은 속성을 갖도록 높이 균형 트리에 데이터를 저장하는 것이다.시간 복잡도가 O(log N)이므로 선형 검색보다 훨씬 빨라진다검색 횟수가 증가하면 이 정도..