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 변수로 구성된다. 자손 노드 포인터를 저장하기 위해 맵이나 벡터를 사용할 수 있다. c struct Trie { map ch; //