자료구조·2025년 7월 1일
Bloom Filter: '없다는 건 확실해, 있다는 건... 글쎄?' (확률적 자료구조)
엄청난 데이터를 아주 적은 메모리로 검사하는 방법. 100% 정확도를 포기하고 99.9%의 효율을 얻는 확률적 자료구조의 세계. 비트코인 지갑과 스팸 필터는 왜 이것을 쓸까요?
#Data Structure#Algorithm#Big Data#Probability
개발과 기술에 대한 이야기를 기록합니다.
엄청난 데이터를 아주 적은 메모리로 검사하는 방법. 100% 정확도를 포기하고 99.9%의 효율을 얻는 확률적 자료구조의 세계. 비트코인 지갑과 스팸 필터는 왜 이것을 쓸까요?
문자열 검색에 특화된 트리 자료구조. 접두사 트리(Prefix Tree)라고도 불리는 Trie의 구조와 삽입/검색 과정, 그리고 메모리 효율을 극대화한 Radix Tree까지 다뤄봤습니다.
이진 탐색 트리(BST)가 편향되는 것을 막는 마법. 5가지 불변 규칙(5 Rules)부터 회전(Rotation), 그리고 AVL 트리와의 비교까지. 왜 OS 스케줄러는 이 트리를 선택했을까요?
