m2ndy 개발 블로그

[Next.js]Trie를 사용해서 네트워크 요청 없이 자동완성 구현하기(Typescript, Zustand) 서비스를 운영하면서 드는 고민 중 하나는 서버 비용이 아닐까 싶어요. 크루위키 서비스를 운영하면서 매달 지출되는 비용이 생각보다 많이 나오더라구요. 클라이언트 측에서 네트워크 요청 횟수를 크게 줄일 수 있는 방법은 없을지 고민하다가, 검색 input을 활용해 보면 좋겠다는 생각이 들었습니다. 동료들과 했던 자료구조 스터디에서 Trie 자료구조를 학습했던 적이 있는데요, Trie 자료구조는 O(N) (N : 문자열의 길이)의 시간 복잡도를 가지고 있어 자동 완성이나 사전 검색 등 문자열을 사용하는 곳에서 자주 활용된다고 합니다. [Typescript] Trie (트라이) 자료구조 직접..

프로젝트에서 자동 완성 컴포넌트를 구현하면서 트라이 자료구조를 접했는데 이번 기회에 직접 구현해보려 한다. 언어는 타입 안정성을 위해 Typescript를 사용했다. Trie (Prefix Tree)Trie는 문자열을 빠르게 탐색할 수 있는 자료구조로, 트리 형태로 구성된다. Prefix tree라고도 불린다.각 노드는 문자열의 한 글자를 나타내며, 루트부터 마지막 노드까지의 경로가 문자열을 구성한다. 해시 테이블에 비해 접두사 기반의 검색에서 더 효율적이다.문자열을 각 노드에 저장하고 메모리를 사용하지만 탐색 속도가 O(N)으로 매우 빠른 편이다. 따라서 자동 완성이나 사전 검색, 맞춤법 검사와 같이 문자열을 활용하는 기능에 주로 사용된다. 시간 복잡도Operation Average WorstIn..