반응형
목차
📍 정의 및 특징
단어들을 사전 형태로 생성 후,
트리의 부모-자식 노드 관계 이용해 빠르게 문자열을 검색하는 알고리즘
- N진 트리 : 문자 종류 개수에 따라 N 결정 (예 : 알파벳 - 26진 트리)
- Map Interface 사용 (computeIfAbsent
, getOrDefault
)
- 문자열 집합이 크고 다양한 검색이 필요한 경우 효율적
- 시간 복잡도 : O(N) (N : 검색하려는 문자열의 길이)
📍 활용 사례
: 검색어 자동 완성, 사전 검색, 문자열 검사 등
📍 실행 과정
: Trie에 문자열 저장 → 문자열 검색
- 루트 노드, 공백 유지 (= 빈 문자열)
- 검색 노드, 공백 상태면 신규 노드 생성하고, 아니면 이동
➕ 예제
(참고)
- Do it 알고리즘 코딩 테스트 자바편
반응형
'코테 > 알고리즘' 카테고리의 다른 글
LIS (최장 증가 부분 수열) (0) | 2023.07.19 |
---|---|
LCS (최장 공통 부분 수열) (0) | 2023.07.06 |
최소 신장 트리 (MST) - 크루스칼, 프림 (0) | 2023.06.27 |
플로이드-워셜 (0) | 2023.06.26 |
벨만-포드 (0) | 2023.06.26 |