[기술 면접] 10. 트라이(Trie) 자료구조에 대해서 알고 계신가요?

제목을 입력해주세요 복사본 13 001 1 1

저번 시간에 이어, 이번엔 트라이(Trie) 자료구조에 대한 질문을 알아보도록 하겠습니다. 트라이(Trie) 자료구조는 문자열과 관련된 문제를 해결할 수 있는지, 해당 자료구조에 대한 이해를 확인하는 질문입니다. 출제 빈도가 높진 않지만, 중요한 자료구조이니 숙지하고 가시길 권해드립니다.

트라이(Trie) 자료구조에 대해서 알고 계신가요?

Q: 트라이(Trie) 자료구조에 대해서 알고 계신가요?

트리 자료구조 중 하나로 문자열을 저장하고 탐색하는 데 유용한 자료구조입니다.

각 노드는 Key와 Value로 구성 되는 Map을 가지고 있으며, Key는 알파벳, Value는 각 Key에 해당하는 자식 노드들을 의미합니다.

루프 노드부터 리프 노드까지 연결하여 검색된 문자열을 찾을 수 있습니다.



Q: 어떤 상황에서 트라이(Trie) 자료구조가 사용되나요?

사전 검색이나 자동 완성, 압축이나 인코딩같이 대량의 문자열을 다룰 때 사용될 수 있습니다.



Q: 트라이(Trie)의 장단점에 대해 말씀해보세요.

문자열 검색을 빠르게 할 수 있지만, 각 노드에서 자식들에 대한 포인터들을 배열로 저장하고 있기 때문에 공간복잡도가 크다는 단점이 있습니다.



마치며

이번 시간엔 트라이(Trie) 자료구조에 대한 질문들을 알아보았습니다.

다음 시간엔, 정렬 알고리즘에서의 안정성(Stability)에 대한 질문을 알아보겠습니다.

image 31

Leave a Comment