Trie(트라이) = radix tree = prefix tree = digital search tree 탐색이라는 뜻의 retrieval에서 trie를 따온 것. 문자열 집합을 표현하는 트리 자료구조. 하나하나 비교가 아닌 key로 노드를 탐색. 원하는 원소를 찾는 작업을 O(M)에 해결 이진트리는 O(logN)*문자열의 길이 M => O(MlogN) 빠르지만 저장공간의 크기가 매우 크다.(자식들의 포인터를 모두 배열로 저장하고 있기때문.) 문자열 검색 문제에서 입력되는 문자열이 많을 경우 사용. 적용되는 기능. 검색엔진 사이트에서 제공하는 자동완성 및 검색어 추천기능에서 Trie 알고리즘 사용. 맞춤법 검사, IP라우팅 (라우터에서 packet을 포워딩해줄때 다음 라우터로 경로를 결정하기 위해 패킷의..