2. 트라이

• 트라이는 문자열 검색을 빠르게 실행할 수 있도록 설계한 트리 형태의 자료구조이다.

✅ 트라이의 핵심 이론

• 트라이는 일반적으로 단어들을 사전의 형태로 생성한 후 트리의 부모 자식 노드 관계를 이용해 검색을 수행한다.

트라이의 특징

• N진 트리: 문자 종류의 개수에 따라 N이 결정된다. 예를 들어 알파벳은 26개의 문자로 이뤄져 있으므로 26진 트리로 구성된다.

• 루트 노드는 항상 빈 문자열을 뜻하는 공백 상태를 유지한다.

• 예시: 영단어 apple, air, apply를 순서대로 트라이 자료구조에 삽입하는 그림이다.

→ 먼저 루트 노드는 공백을 유지하고 apple의 각 알파벳에 해당하는 노드를 생성한다. 그다음으로 air를 삽입할 때는 루트 노드에서부터 검색한다. a 노드는 공백 상태가 아니므로 이동하고, i와 r은 공백상태이므로 신규 노드를 생성한다. apply를 삽입할 때도 검색 노드가 공백 상태이면 신규 노드를 생성하고, 아니면 이동하는 원리로 트라이 자료구조를 구현한다.

📰 예시 코드 (백준 14425번)

문자열 찾기

문제

총 N개의 문자열로 이루어진 집합 S가 주어진다.

입력으로 주어지는 M개의 문자열 중에서 집합 S에 포함되어 있는 것이 총 몇 개인지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다.

다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다.