트라이 (Trie)
목차
📍 정의 및 특징
단어들을 사전 형태로 생성 후,
트리의 부모-자식 노드 관계 이용해 빠르게 문자열을 검색하는 알고리즘
- N진 트리 : 문자 종류 개수에 따라 N 결정 (예 : 알파벳 - 26진 트리)
- Map Interface 사용 (computeIfAbsent , getOrDefault)
- 문자열 집합이 크고 다양한 검색이 필요한 경우 효율적
- 시간 복잡도 : O(N) (N : 검색하려는 문자열의 길이)
📍 활용 사례
: 검색어 자동 완성, 사전 검색, 문자열 검사 등
📍 실행 과정
: Trie에 문자열 저장 → 문자열 검색
- 루트 노드, 공백 유지 (= 빈 문자열)
- 검색 노드, 공백 상태면 신규 노드 생성하고, 아니면 이동
➕ 예제
5052번: 전화번호 목록
첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가
www.acmicpc.net
[백준/JAVA] 14425번: 문자열 집합
🔺 문제 14425번: 문자열 집합 첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다. 다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다. 다음 M개의 줄에는 검사
bono039.tistory.com
(참고)
[자료구조] Trie(트라이)-2 : 자바로 구현하기
안녕하세요. 개발개입니다. 지난 시간 기초 개념에 이어, Trie를 자바로 구현하는 과정을 알아보겠습니다. 구현 과정에서 람다를 사용하기 때문에 Java8이상으로 진행합니다. [KR/자료구조] - [자료
the-dev.tistory.com
[Algorithm] Trie를 Java로 구현해보자!
안녕하세요 coding-knowjam입니다. 오늘은 검색할 때 O(N)의 시간 복잡도를 가지는 Trie를 구현해보겠습니다. 1. Trie란? Trie는 일반적인 Tree자료구조와 같은 모양이지만 저장하는 값이 다른 형태입니다.
codingnojam.tistory.com
- Do it 알고리즘 코딩 테스트 자바편