Algorithm Guidecomplexity: O(m) (문자열 길이)

트라이 (Trie)

문자열을 글자 단위로 가지에 저장하는 접두사 트리입니다. 공통 접두사를 공유해 자동완성·사전·접두사 검색을 문자열 길이 O(m)에 처리합니다.

01 알고리즘 작동 원리 탐색

Interactive Step-by-Step

HOVER OR SCROLL

Trie · 접두사 트리

트라이 시작. 문자열을 글자 단위로 가지에 저장하고, 공통 접두사는 같은 길을 함께 씁니다.

Logic Node1 / 6

Live Python

1class TrieNode:

2 def __init__(self):

3 self.children = {}

4 self.is_end = False

6class Trie:

7 def __init__(self):

8 self.root = TrieNode()

9 def insert(self, word):

10 node = self.root

11 for ch in word:

12 node = node.children.setdefault(ch, TrieNode())

13 node.is_end = True

14 def search(self, word):

15 node = self.root

16 for ch in word:

17 if ch not in node.children:

18 return False

19 node = node.children[ch]

20 return node.is_end

02 쉽게 이해하기

For Everyone

🔑비유

사전의 가지치기 색인 — 같은 첫 글자로 시작하는 단어들은 한 길을 공유합니다.

💡쉽게 말하면

문자열을 글자 단위로 가지에 저장해 공통 접두사를 함께 쓰는 트리예요.

단어 길이 O(m)에 찾고, 특정 접두사로 시작하는 단어들을 빠르게 모읍니다.

📍어디에 쓰나

–검색어 자동완성
–사전·맞춤법 검사
–IP 라우팅

03 파이썬 구현 코드

트라이 (Trie)의 핵심 로직을 담은 표준 구현 예시입니다. 가급적 간결하고 읽기 쉬운 코드로 작성되었습니다.

core_implementation.py

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for ch in word:
            node = node.children.setdefault(ch, TrieNode())
        node.is_end = True

    def search(self, word):
        node = self.root
        for ch in word:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return node.is_end