트라이

트라이(Trie)는 문자열의 집합을 표현하는 트리 자료구조입니다.

STL로 문자열의 집합을 표현하려면 set<string>을 사용합니다.

set에서 검색할 때는 O(lgN)번 비교연산을 진행하지만

string은 한 번 비교연산을 할 때마다 틀릴 때까지 앞글자부터 하나하나 비교를 하기에

문자열의 길이가 M일 경우 시간복잡도가 O(MlgN)이 됩니다.

이를 O(M)만에 탐색하기 위해 트라이 자료구조를 사용합니다.

트리 형태를 이용하여 다음에 나올 글자에 해당하는 노드가 있을 경우

그 노드로 바로 이동하여 다음 글자를 탐색합니다.

그 노드로 바로 이동하기 위해 다음 글자를 가능한 글자들을 가리키는 여러 개의 포인터 배열이 필요한데

이는 많은 메모리를 낭비하게 되는 단점이 있습니다.

이렇기 때문에 트라이를 사용해야하는 문제에서는 입력 데이터의 전체 글자를 제한한다는 조건이 들어가며

메모리를 계산 해 본 뒤 이 자료구조를 구현하여 사용해 볼 수 있습니다.

이는 추후 아호코라식 알고리즘에서 응용하여 사용하는 자료구조입니다.

기본 문제

9934번: 완전 이진 트리

5052번: 전화번호 목록

5670번: 휴대폰 자판