hyunkookim 님의 블로그

745. Prefix and Suffix Search 문제 LeetCode 745. Prefix and Suffix Search를 해결하는 Trie 기반 풀이를 제공해드릴게요.접두사(prefix)와 접미사(suffix)를 동시에 만족하는 단어를 빠르게 찾기 위해, 특수한 방식으로 Trie를 구성합니다.✅ 핵심 아이디어:모든 단어에 대해 "suffix#prefix" 형태로 key를 만들어서 Trie에 저장합니다.예시단어 "apple" → "e#apple", "le#apple", ..., "#apple" 등으로 여러 key 생성검색할 때 "suff#pref" 형식으로 Trie에서 찾기✅ 완성된 코드 (딕셔너리 기반 Trie 사용)class TrieNode: def __init__(self): ..

Trie (접두사 트리) - 동기 우리가 왜 trie가 필요한지에 대한 동기를 살펴봅시다. 예를 들어, 오이(cucumbers), 콜리플라워(cauliflower), 토마토(tomatoes) 같은 여러 채소가 들어 있는 큰 상자가 있다고 해 봅시다.만약 이 채소들을 이름 기준으로 정리하고 싶다면, 우리는 먼저 더 작은 상자들을 준비해서 알파벳 각 글자를 이름표로 붙일 수 있을 거예요.예를 들어, "A"로 시작하는 채소들은 "A" 상자에 넣는 식으로요. 접두사(prefix)가 같은 단어들을 처리하는 방식Trie에서는 중복되는 접두사를 공유된 경로로 나타내어 공간을 절약하고 효율적으로 구조화할 수 있음 Trie의 계층 구조: 상자 안에 또 상자를 넣는 방식으로, 단어의 각 글자마다 하나씩 노드를 추가해 나가..

212. Word Search II https://leetcode.com/problems/implement-trie-prefix-tree/description/ : 208. Implement Trie (Prefix Tree) https://youtu.be/asbcE9mZz_U?si=7ovXqcPW-mJDtg7h   class TrieNode: def __init__(self): self.children = {} # 자식 노드를 저장하는 딕셔너리 (예: {'a': TrieNode()}) self.isWord = False # 현재 노드가 단어의 끝인지 여부를 나타내는 플래그 def addWord(self, word): cur = self # 현재 노드에..

211. Design Add and Search Words Data Structure https://youtu.be/BTf05gs_8iU?si=Oj37OnsdmiSq4Yfd class TrieNode(): def __init__(self): self.children = {} # a: TrieNode self.word = False # 현재 노드가 단어의 끝인지 표시class WordDictionary: def __init__(self): self.root = TrieNode() # Trie의 루트 노드 초기화 def addWord(self, word: str) -> None: cur = self.root # 루트 노드부터 시작 ..

208. Implement Trie (Prefix Tree) https://youtu.be/oobqoCJlHA0?si=rB7vqpOg4d0DiFd1 https://youtu.be/j7Zkw5XWe_Q?si=-yC7nuoxBULmLBuD 이 문제는 Trie(트라이) 자료 구조를 구현하는 것입니다. Trie는 문자열을 효율적으로 저장하고 검색하기 위해 사용되는 트리 형태의 자료 구조입니다. 이 자료 구조는 주로 자동완성, 단어 검색, 접두사 검색과 같은 작업에서 사용됩니다.  Code  # TrieNode 클래스: Trie의 각 노드를 정의class TrieNode: def __init__(self): self.children = {} # 자식 노드를 저장할 해시맵. 키는 문자, 값은 T..