0. 들어가며 BloomFilter에 대해 알아보게 된 계기대규모 사용자 기반을 가진 서비스에서 사용자들에게 개인화된 정보를 제공하는 경우, 개인화된 정보를 효율적으로 저장하고 이를 빠르게 처리해야하는 것이 중요합니다. 하지만 DB만을 저장소로 사용하다보면 데이터가 쌓일수록 저장공간도 많이 사용해야하고, 트래픽이 많아질 수록 성능 저하가 생길 수 있습니다. 이러한 문제를 해결하기 위해 메모리를 효율적으로 사용하면서도 빠르게 특정 원소가 집합에 포함되어있는지 확인이 가능한 BloomFilter라는 자료구조를 도입해보았고, 도입하는 과정에서 BloomFilter에 대해 알아본 내용들을 정리해보려합니다.이번 글에서 다룰 내용 소개이번 글에서는 다음과 같은 내용을 다룹니다.BloomFilter가 무엇인지Bloo..

우선순위 큐와 Heap 우선순위 큐는 일반적인 큐와 다르게 우선순위가 높은 데이터가 먼저 나갈 수 있도록 만들어진 자료구조입니다. 그래서 어떻게 구현하는데? 우선순위 큐는 배열 또는 연결리스트을 단순하게 사용하여도 구현이 가능합니다. 배열과 연결리스트의 맨 앞 원소부터 차례대로 우선순위가 높은 data를 넣는다면 어렵지않게 우선순위 큐를 구현할 수 있습니다. 이러한 방식으로 우선순위 큐를 구현하게 되면 우선순위에 맞춰 data를 알맞은 자리에 삽입해야 하기 때문에 이 과정이 O(n)의 시간복잡도가 소요됩니다. 하지만 heap 자료구조를 사용한다면 조금 더 효율적인 방식으로 우선순위 큐를 구현할 수 있습니다. heap을 사용한다면? 우선 heap이 무엇인지에 대해 알아보겠습니다. heap 이란? 힙(hea..