트라이 그림을 그릴 수 있는지가 아니라, prefix 이점과 메모리 비용 사이를 어떤 기준으로 끊는지 가르려는 질문이다.
트라이는 루트에서 문자 하나씩을 간선으로 따라가며 문자열을 저장하는 트리 자료구조다. 같은 접두사를 가진 문자열들은 같은 경로를 공유하기 때문에, 'apple', 'apply', 'april'이 어디까지 같이 흐르고 어디서 갈라지는지가 구조에 그대로 드러난다. 그래서 길이 k짜리 문자열 조회나 prefix 조회를 O(k)에 처리할 수 있어 자동완성에 잘 맞는다. 대신 노드마다 자식 참조를 들고 있어 어휘 크기와 알파벳 범위가 커지면 메모리가 빠르게 부풀어, 자식 구조(배열·해시), 단어 종료 플래그, 압축 트라이(radix tree) 채택 같은 설계 선택이 같이 따라붙는다.
해시맵 기반 검색을 트라이로 옮기며 prefix·메모리 사이의 균형을 잡아 본 경험이 있다면 자료구조 선택 사례로 연결할 수 있다
대용량 사전에서 압축 트라이·DAWG로 메모리를 줄여 본 적이 있다면 운영 트레이드오프 관점으로 엮을 수 있다
한글·이모지 같은 다바이트 문자열을 트라이에 담아 본 경험이 있다면 자식 구조 선택 기준으로 말할 수 있다
아직 공개된 답변이 없어요. 첫 공개 답변을 남겨보세요.