저번 시간에 이어, 이번엔 트라이(Trie) 자료구조에 대한 질문을 알아보도록 하겠습니다. 트라이(Trie) 자료구조는 문자열과 관련된 문제를 해결할 수 있는지, 해당 자료구조에 대한 이해를 확인하는 질문입니다. 출제 빈도가 높진 않지만, 중요한 자료구조이니 숙지하고 가시길 권해드립니다.
Q: 트라이(Trie) 자료구조에 대해서 알고 계신가요?
트리 자료구조 중 하나로 문자열을 저장하고 탐색하는 데 유용한 자료구조입니다.
각 노드는 Key와 Value로 구성 되는 Map을 가지고 있으며, Key는 알파벳, Value는 각 Key에 해당하는 자식 노드들을 의미합니다.
루프 노드부터 리프 노드까지 연결하여 검색된 문자열을 찾을 수 있습니다.
Q: 어떤 상황에서 트라이(Trie) 자료구조가 사용되나요?
사전 검색이나 자동 완성, 압축이나 인코딩같이 대량의 문자열을 다룰 때 사용될 수 있습니다.
Q: 트라이(Trie)의 장단점에 대해 말씀해보세요.
문자열 검색을 빠르게 할 수 있지만, 각 노드에서 자식들에 대한 포인터들을 배열로 저장하고 있기 때문에 공간복잡도가 크다는 단점이 있습니다.
마치며
이번 시간엔 트라이(Trie) 자료구조에 대한 질문들을 알아보았습니다.
다음 시간엔, 정렬 알고리즘에서의 안정성(Stability)에 대한 질문을 알아보겠습니다.
답글 남기기