GW LABS

이번 포스팅에서는 트라이에 대해 알아보려고 한다. 생소한 이름 때문에 어떤 역사가 있는 지 찾아봤더니 재미있는 일화가 있었다. 트라이는 René de la Briandais에 의해 개념이 소개되고, Edward Fredkin에 의해 reTRIEval(검색)이라는 단어에서 trie라고 명명되었다. 처음 발음할 때에는 트리라고 불러졌는데, 트리(tree)와 구분하기 위해서 트라이로 발음하기 시작했다고 한다. 그럼 어떤 자료구조인지 자세히 알아보자. 1. Trie 트라이는 문자열을 빠르게 검색하기 위해 고안되었다. 기본적인 구조는 트리와 비슷한데 차이점은 노드에 문자열을 문자단위로 분해하여 저장한다는 점이다. 위의 그림과 같이 한 글자씩 트리를 따라가며 검색을 하는 구조이다. 한 글자씩 저장하지 않고 트라이의..