- 트라이: 검색 트리의 일종으로 일반적으로 키가 문자열인, 동적 배열 또는 연관 배열을 저장하는 데 사용되는 정렬된 트리 자료구조
- 특히 자연어 처리 분야에서 문자열 탐색을 위한 자료구조로 널리 쓰인다
- 검색을 뜻하는 'retrieval'에서 따옴
- 다진 트리의 형태
- 각 문자열 길이만큼만 탐색하면 원하는 결과 찾을 수 있다
208. Implement Trie (Prefix Tree)
- TrieNode 클래스 생성해 딕셔너리로 노드 값 정보, 불리안으로 해당 노드에서 단어 완성 여부 정보를 각 노드에 담는다
-> 삽입이나 검색하려는 문자열 갯수만큼 반복하여 각 노드의 딕셔너리 확인하며 필요한 작업 수행
336. Palindrome Pairs
- 부르트 포스 -> 시간 초과 O(n^2)
- 트라이 구현 -> 입력값 철자 역순으로 트라이 구성하고 탐색은 순서대로 -> 탐색이 진행된다 = 그 철자까지 팰린드롬
1. 끝까지 탐색했을 때 word_id 값 있는 경우
2. 끝까지 탐색했을 때 palindrome_word_ids 값 있는 경우
3. 탐색 중간에 word_id 값 있고, 입력값 기준 나머지 철자들이 팰린드롬인 경우
- @staticmethod 데코레이터로 정의된 메소드는 클래스와 독립적인 함수로서 의미를 강하게 갖는다
- 사실상 클래스 바깥에 함수를 별도 선언한 것과 같아 클래스 메소드처럼 자유롭게 클래스 인스턴스 접근 제한
'CS > algorithm & data structure' 카테고리의 다른 글
| [파이썬 알고리즘 인터뷰] 이진 검색 (0) | 2022.05.03 |
|---|---|
| [파이썬 알고리즘 인터뷰] 정렬 (0) | 2022.04.28 |
| [파이썬 알고리즘 인터뷰] 힙 (0) | 2022.04.06 |
| [파이썬 알고리즘 인터뷰] 트리 (0) | 2022.04.04 |
| [파이썬 알고리즘 인터뷰] 최단 경로 문제 (0) | 2022.03.16 |
