Trie 문자열 검색 문제에 특화된 트리 형태의 자료구조. 원하는 문자열을 O(m) (m = 문자열의 길이) 시간복잡도로 찾을 수 있다. struct Trie 내의 Trie 포인터 배열을 가지고 해당 키에 맞는 포인터로 이어지는 구조. Trie는 검색 후보 문자열을 하나의 트리로 만들어서, 한번의 검색 O(m) 만으로 문자열의 존재 여부를 검색 가능하다. 주의 항상 첫번째 root 노드는 빈칸이다. 트라이 객체마다 트라이 포인터 배열을 경우의 수만큼 가져야 하므로 공간복잡도가 매우 커질 수 있다. 공간복잡도 : O(key의 경우의수 * 포인터 크기 * 전체 트라이에 존재하는 노드 수) 필수 1) 다음 두 가지를 가지고 있어야 한다. - child (자식 노드를 담는 배열) - isTerminal (어떤 ..
