목록2024/08/23 (1)

Techbrad

[자료구조] 접두사에 강한 트라이(Trie)

코테 공부를 하다가 접두사 관련 시간 초과가 계속 나서 문제를 찾아보다가 Trie자료구조를 알게되었다. 일반 검색할때 자동완성에 이러한 자료 구조가 쓰여졌다는 것이 흥미로웠다. 그래서 ChatGPT에 물어보았다.ChatGPT 답변Trie 자료구조는 문자열이나 텍스트 데이터를 효율적으로 저장하고 검색하는 데 사용되는 트리 기반 자료구조입니다. 주로 접두사와 관련된 문제를 해결하는 데 유리한 특징을 가지고 있습니다. 예를 들어, 많은 단어들에서 같은 접두사가 있을 때, 그 부분을 공유하여 공간을 절약하고 빠르게 검색할 수 있습니다.Trie의 구조Trie는 각 노드가 문자를 가지고 있으며, 루트에서부터 자식 노드를 따라가면서 하나의 문자열을 구성합니다. 이때, 각 노드는 해당 문자가 접두사가 되는 위치에 있습..
Programming/자료구조 및 알고리즘 2024. 8. 23. 22:30
이전 Prev 1 Next 다음