목록2025/04/10 (1)

Coding 01

트라이 자료구조

트라이 자료구조는 문자열을 효율적으로 저장하고 검색하기 위한 트리 형태의 자료구조이다.트라이는 문자열을 탐색할 때 단순히 비교하는 것에 비해서 효율적으로 찾을 수 있는데, 정점이 자식에 대한 링크를 모두 가지고 있어서 저장공간을 많이 사용한다, 주로 검색어 자동완성이나 사전 찾기 기능을 구현할 때 사용한다.트라이에서 각 노드는 하나의 문자를 나타낸다. 루트에서 특정 노드까지의 경로가 하나의 문자열이라고 생각하면 된다.같은 접두사를 가진 문자열들은 같은 경로를 가진다. 각 노드에는 단어의 끝을 표시하는 불린 값이 있다. 트라이 자료구조를 사용하면 문자열 검색이 매우 빠르다. 접두사 검색에 효율적이라 자동완성을 사용하기에 좋다.하지만 앞에서 말했던것 처럼 메모리 사용량이 많을 수 있고, 구현이 복잡하다. 트..
기술면접 2025. 4. 10. 09:48
이전 Prev 1 Next 다음