Study/Data Structure
-
[Data Structure] 자료구조 - ArrayStudy/Data Structure 2020. 9. 21. 23:47
1. Introduction to Arrays Array는 item들의 collection이 메모리에 연이은 위치에저장된다. 여러 같은 type의 여러 item을 같이 저장하는 것이다. 기본 값에 offset을 추가하여 각 요소의 위치를 쉽게 계산할 수 있다. 더보기 offset: 기준이 되는 주소에 더해지는 값 각 element는 array의 index로 식별할 수 있다. Array의 장점 1. Array에서는 element의 random access가 된다. 이 말은 위치로 element에 접근하는 것이 빠르다는 것이다. 2. Array는 성능에 큰 차이를 만들 수 있는 더 나은 캐시 locality를 가지고 있다. 더보기 locality: 기억 장치 내의 정보를 균일하게 접근하는 것이 아닌 어느 한..
-
구현을 통한 Bloom Filter 알아보기 with Python3Study/Data Structure 2020. 6. 11. 22:39
Bloom Filter를 구현하기에 앞서 Bloom Filter의 정의를 보겠습니다. 위키피디아에 따르면 "Bloom Filter는 원소가 집합에 속하는지 여부를 검사하는데 사용되는 확률적 자료구조이다. Bloom Filter의 핵심은 바로 '확률적 자료구조'라는데 있습니다. '블룸 필터에 의해 어떤 원소가 집합에 속한다고 판단된 경우 실제로는 원소가 집합에 속하지 않는 긍정 오류가 발생하는 것이 가능하지만, 반대로 원소가 집합에 속하지 않는 것으로 판단되었는데 실제로는 원소가 집합에 속하는 부정 오류는 절대로 발생하지 않는다는 특성이 있다'라고 합니다. 예를 들어 원소 'dog'이 집합에 속한다고 알려주지만 실제로는 'dog'이 집합의 원소가 아닐 수 있다는 것 입니다. 그리고 'cat'이라는 원소가 ..
-
Trie 자료구조Study/Data Structure 2020. 6. 11. 19:21
https://en.wikipedia.org/wiki/Trie를 참고하면 digital tree 또는 prefix tree라고 하는 trie는 일종의 검색 트리입니다. 동적인 set을 저장하거나 연관있는 배열을 저장할 때 쓰입니다. key는 일반적으로 문자열을 저장합니다. binary search tree와는 다르게 노드는 관련된 키를 저장하지 않습니다. 대신 트리의 위치가 키를 정의하는 방식입니다. 그래서 키는 트리 구조 전체에 분산되어 있습니다. 노드의 모든 하위 항목에는 해당 노드와 연관된 문자열의 공통 접두사가 있습니다. 루트는 빈문자열과 연관되어 있습니다. 위 그림과 같이 "te"의 하위 항목인 "tea", "ted", "ten"은 "te"라는 공통 접두사가 있다고 보시면 됩니다. 아래는 위키피..