☘️ 트라이(Trie) 트라이 정의 트라이는 트리 형태로 되어 있는 자료구조이다. 트라이 문자열 저장 문자열을 효율적으로 탐색하기 위한 자료구조 이전 정점으로부터 더해진 문자열 정보 가짐 트라이 특징 검색어 자동완성, 사전 찾기 트라이는 검색어 자동완성, 사전 찾기 등에서 활용된다. 효율적인 문자열 탐색 단순하게 문자열을 비교하여 탐색하는 것보다 효율적이게 찾을 수 있다. 탐색 시간 문자열을 탐색, 삽입하는 시간 복잡도는 문자열의 길이만큼 소요된다. 문자열 길이: L 시간 복잡도: O(L) 저장공간 각 정점이 자식에 대한 링크를 전부 가지고 있어 저장공간이 많이 차지한다는 단점이 있다. 트라이 구조 특징 빈 루트 트라이의 Root는 문자열이 없는 비어있는 상태이다. 간선(링크) 키 값 각 간선(링크)는 ..