Skip to content
Beside the Wheel

태그: 자료구조

총 5개의 글이 있습니다.
KD-tree
자료구조
정렬된 배열에서 특정 값을 찾을 때, 전부 다 순회할 때의 시간 복잡도는 O(n)이다. 하지만 배열이 정렬되어 있다는 사실을 이용하면, 중간값과 비교해서 절반을 날릴 수 있다. 이것이 이진 탐색이고, O(log n) 시간 복잡도를 가진다. 정렬된 배열에서 쿼리 값 q에 가장 가까운 원소를 찾는 최근접 이웃(nearest neighbor) 탐색도 같은 원리이다. brute force로 하면 모든 원소와의 거리를 계산해야 하니 O(n)이다. 하지만 배열이 정렬되어 있으면, q가 배열에서 어디쯤 들어갈지를 이진 탐색으로 O(log n)에 찾을 수 있다. q가 들어갈 위치를 찾았으면, 가장 가까운 원소는 그 위치의 바로 왼쪽 아니면 오른쪽에 있다. 이 문제는 1차원에 해당한다. 하지만 2차원 평면에 점들이 흩어져
LSM Tree
자료구조
LSM 트리는 로그파일 기반으로 작성되는 방식의 파일 구조이다. LSM 트리는 Append-only 방법이어서 쓰기작업의 효울성이 좋다. 작동 방식 쓰기 작업 LSM 트리는 데이터를 disk에 바로 쓰지 않고, 정렬된 메모리 테이블(memTable)과 로그파일에 먼저 쓴다. 메모리 테이블은 주로 레드-블랙 트리를 사용하여 키-값 쌍을 기반으로 정렬된 구조를 유지한다. Memtable이 설정된 임계값에 도달하면, 그 내용은 디스크에 파일로 저장됩니다. 이때 데이터는 정렬된 상태로 저장되기 떄문에, 이 파일을 SSTable(Sorted String Table)이라고 부른다. SSTable은 불변성을 지니며, 한 번 기록된 후에는 변경되지 않는다. 이 구조는 데이터 일관성을 보장하며 압축이 진행되는 중에도
Trie
자료구조
트라이는 문자열을 저장하고 효율적으로 검색하기 위한 트리 기반의 자료구조이다. 트라이는 루트 노드부터 시작하고, 각 노드는 문자를 나타낸다. 그리고 문자열은 루트에서 리프 노드까지의 경로로 표현된다. 트라이 자료구조를 사용하면 문자열을 매우 빠르게 검색할 수 있다. 특히 접두사 검색에 효율적이다. (O(m) 시간, m은 문자열 길이). 큰 메모리가 필요하다는 단점이 있다. 접두사를 바탕으로 한 자동 완성이나, 문자열 매칭을 위해 사용할 수 있다. 구현 트라이의 한 노드를 구성하는 객체는 자손 노드를 가리키는 포인터 목록과, 문자열의 끝인지를 나타내는 bool 변수로 구성된다. 자손 노드 포인터를 저장하기 위해 맵이나 벡터를 사용할 수 있다. struct Trie { map&x3C;char, Trie*>