hyunkookim 님의 블로그

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

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..