0Pricing
DSA Interview Prep · 강의

TrieNode 클래스: 삽입과 검색

자식 dict와 is_end 플래그를 갖는 TrieNode를 만들고, 삽입과 정확한 검색을 구현하며, 단어 길이를 m이라 할 때 연산당 O(m) 시간임을 분석합니다.

TrieNode 클래스: 삽입과 검색은(는) CoddyKit의 무료 DSA Interview Prep 강의입니다. 이것은 4개 중 1번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 DSA Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.

Trie란 무엇인가

Trie(접두사 트리)는 각 노드가 하나의 문자를 나타내는 트리 형태의 자료 구조입니다. 단어는 루트에서 리프까지 문자를 연결해 저장합니다. 루트는 빈 문자열을 나타냅니다. 루트에서 is_end = True인 노드까지의 각 경로는 저장된 단어 하나를 나타냅니다. Trie는 접두사 기반 조회에 적합합니다. 예를 들어 autocomplete, 철자 검사, IP 라우팅 등에 사용할 수 있으며, 이러한 사용 사례에서는 해시 맵보다 뛰어난 성능을 냅니다.

TrieNode 클래스 설계

TrieNode에는 두 개의 필드가 있습니다. children은 문자를 자식 TrieNode에 매핑하는 사전이고, is_end는 이 노드가 저장된 단어의 끝인지 표시하는 불리언 값입니다. 고정된 26자 배열 대신 사전을 사용하면 어떤 문자 집합에도 적용할 수 있고, 희소한 Trie에서 메모리를 절약할 수 있습니다. Trie의 각 노드는 그 아래에 있는 단어에서 정확히 하나의 문자 위치를 나타냅니다.

class TrieNode:
    def __init__(self):
        self.children = {}  # char -> TrieNode
        self.is_end = False  # True if a word ends here

class Trie:
    def __init__(self):
        self.root = TrieNode()
    
    def __repr__(self):
        return f'Trie(root with {len(self.root.children)} children)'

t = Trie()
print(t)  # Trie(root with 0 children)

삽입 연산

단어를 삽입하려면 루트에서 시작해 순회하면서 현재 노드의 children에 아직 존재하지 않는 각 문자에 대해 새로운 TrieNode를 만듭니다. 모든 문자를 처리한 후 마지막 노드에서 is_end = True로 설정합니다. 'apple'과 'app'을 삽입하면 a→p→p→l→e 연결이 만들어지고('apple'의 끝이 표시됨), 세 번째 위치의 p도 'app'의 끝임을 나타내도록 표시됩니다.

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 char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end = True

t = Trie()
t.insert('apple')
t.insert('app')
print('Inserted apple and app')
print('app is_end:', t.root.children['a'].children['p'].children['p'].is_end)

검색 연산

정확히 일치하는 단어를 검색하려면 각 문자를 따라 Trie를 순회합니다. 현재 노드의 children에서 문자 하나라도 찾지 못하면 거짓을 반환합니다. 모든 문자를 찾았다면 node.is_end를 반환합니다. 이 값이 참일 때만 정확히 그 위치에서 단어가 끝납니다(단순히 접두사인 경우는 제외됩니다). '접두사가 존재하는지'와 '정확한 단어가 존재하는지'를 구분하는 것은 매우 중요하며, 면접에서 자주 확인하는 내용입니다.

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 c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        node.is_end = True
    
    def search(self, word):
        node = self.root
        for c in word:
            if c not in node.children:
                return False
            node = node.children[c]
        return node.is_end  # must be a complete word

t = Trie()
t.insert('apple')
print(t.search('apple'))   # True
print(t.search('app'))     # False (app not inserted)
print(t.search('orange'))  # False

접두사 검색(starts_with)

starts_with 메서드는 삽입된 단어 중 주어진 접두사로 시작하는 단어가 있는지 확인합니다. search와 동일하게 순회하지만 is_end를 확인하는 대신, 접두사의 모든 문자를 성공적으로 따라가면 즉시 참을 반환합니다. 이는 해당 접두사 경로가 Trie에 존재한다는 뜻입니다.

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 c in word:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        node.is_end = True
    
    def search(self, word):
        node = self.root
        for c in word:
            if c not in node.children: return False
            node = node.children[c]
        return node.is_end
    
    def starts_with(self, prefix):
        node = self.root
        for c in prefix:
            if c not in node.children: return False
            node = node.children[c]
        return True  # prefix path exists

t = Trie()
t.insert('apple')
print(t.starts_with('app'))   # True
print(t.starts_with('ape'))   # False
print(t.search('app'))         # False (not inserted)

시간 및 공간 복잡도

각 Trie 연산(insert, search, starts_with)은 O(m) 시간이 걸리며, 여기서 m은 단어의 길이입니다. 공간 복잡도는 O(문자 집합 크기 × N × M)이며, N은 단어 수이고 M은 평균 단어 길이입니다. 실제로는 접두사를 공유하므로 공간을 크게 줄일 수 있습니다. 해시 맵 기반 children 사전은 희소한 Trie에서 고정된 26자 배열보다 공간을 적게 사용하지만, 조회마다 상수 오버헤드가 약간 더 큽니다.

사전 대신 배열 사용

영문 소문자만 사용한다면 고정 크기 배열 children = [None] * 26을 사용하고, 인덱스는 ord(c) - ord('a')로 계산합니다. 이 방식은 더 빠르고(해시 맵에 비해 자식 조회가 O(1)) 메모리 배치도 예측할 수 있습니다. 문자 집합이 크거나 알려지지 않은 경우(예: Unicode)에는 사전 방식을 사용하고, 영문 소문자만 사용하는 대회형 문제에서는 배열 방식을 사용합니다.

class TrieNodeArray:
    def __init__(self):
        self.children = [None] * 26
        self.is_end = False

class TrieArray:
    def __init__(self):
        self.root = TrieNodeArray()
    
    def insert(self, word):
        node = self.root
        for c in word:
            idx = ord(c) - ord('a')
            if node.children[idx] is None:
                node.children[idx] = TrieNodeArray()
            node = node.children[idx]
        node.is_end = True
    
    def search(self, word):
        node = self.root
        for c in word:
            idx = ord(c) - ord('a')
            if node.children[idx] is None: return False
            node = node.children[idx]
        return node.is_end

t = TrieArray()
t.insert('cat')
print(t.search('cat'))  # True
print(t.search('car'))  # False

삭제 연산

Trie에서 삭제할 때는 세 가지 경우를 처리해야 합니다. (1) 단어가 없음 — 아무 작업도 하지 않습니다. (2) 단어가 존재하지만 다른 단어의 접두사임 — is_end만 해제합니다. (3) 단어가 존재하고 다른 단어의 접두사가 아님 — 아래쪽 노드부터 위쪽으로 삭제하되, 어떤 노드에 다른 자식이 있거나 다른 단어의 끝인 경우 중단합니다. 삭제는 면접에서 거의 출제되지 않지만 개념적으로 알아 두면 좋습니다.

접두사로 시작하는 단어 수 세기

각 노드에 count 필드를 추가하고, 삽입 과정에서 해당 노드를 통과할 때마다 값을 증가시킵니다. 주어진 접두사로 시작하는 단어 수를 세려면 접두사의 끝 노드까지 순회한 후 그 노드의 값을 반환합니다. 이렇게 하면 모든 자식을 순회하지 않고도 O(m) 시간에 autocomplete 조회를 수행할 수 있어 실제 autocomplete 시스템에 유용한 확장이 됩니다.

class TrieNodeCount:
    def __init__(self):
        self.children = {}
        self.is_end = False
        self.count = 0  # words passing through this node

class TrieCount:
    def __init__(self):
        self.root = TrieNodeCount()
    
    def insert(self, word):
        node = self.root
        for c in word:
            if c not in node.children:
                node.children[c] = TrieNodeCount()
            node = node.children[c]
            node.count += 1  # increment on each level
        node.is_end = True
    
    def count_with_prefix(self, prefix):
        node = self.root
        for c in prefix:
            if c not in node.children: return 0
            node = node.children[c]
        return node.count

t = TrieCount()
for w in ['apple','app','application','apply']:
    t.insert(w)
print(t.count_with_prefix('app'))   # 4
print(t.count_with_prefix('appl'))  # 3

Trie와 해시 맵 비교

해시 맵은 평균 O(m) 시간에 정확한 조회를 수행할 수 있지만, 접두사 조회에는 효율적으로 대응하지 못합니다(모든 키를 훑어야 합니다). Trie는 p가 접두사 길이일 때 O(p)에 접두사 조회를 수행하고, 공유된 접두사에 따라 단어를 자연스럽게 묶으며, 해싱이 필요하지 않습니다. 다음과 같은 경우에는 Trie를 사용합니다. 접두사 조회가 잦거나, autocomplete 또는 철자 검사가 필요한 경우입니다. 정확한 조회만 필요한 경우에는 해시 맵을 사용합니다.

실제 시스템에서의 Trie

실제 시스템에서 Trie는 다음과 같이 사용됩니다. autocomplete(Google 검색 추천), 철자 검사기(가장 일치하는 단어 찾기), IP 라우팅(라우터에서의 최장 접두사 일치), T9 예측 입력(문자 구분), DNS 확인자(계층적 도메인 이름 조회) 등이 있습니다. 각 경우에 Trie의 연산당 O(m) 시간과 O(ALPHABET × 노드) 공간이라는 절충은 대규모 환경에서 빠르고 접두사를 고려하는 조회를 수행하기에 적합합니다.

빠른 확인

이 단원에서 배운 자료 구조 및 알고리즘 — 코딩 면접 대비 개념에 대한 이해도를 확인해 보세요.

단원 복습

이 단원에서는 다음을 배웠습니다. TrieNode에는 children 사전과 끝 여부를 나타내는 불리언 값이 있습니다. insert는 문자 단위로 순회하면서 필요한 노드를 만들고 마지막에 끝 표시를 설정합니다. 또한 search는 끝 표시를 확인하지만 starts_with는 접두사 경로의 존재 여부만 확인합니다. 다음에는 접두사 기반 autocomplete와 starts_with 메서드를 더 자세히 살펴봅니다.

자주 묻는 질문

“TrieNode 클래스: 삽입과 검색” 강의는 무료인가요?

네 — “TrieNode 클래스: 삽입과 검색” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 DSA Interview Prep 강의 전체를 잠금 해제할 수 있습니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.

“TrieNode 클래스: 삽입과 검색”에서 뭘 배우나요?

자식 dict와 is_end 플래그를 갖는 TrieNode를 만들고, 삽입과 정확한 검색을 구현하며, 단어 길이를 m이라 할 때 연산당 O(m) 시간임을 분석합니다. 브라우저에서 직접 실행하는 실습 코드로 DSA Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.

DSA Interview Prep을(를) 시작하는 데 경험이 필요한가요?

사전 경험은 필요하지 않습니다. CoddyKit의 DSA Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 1번째 강의입니다.

“TrieNode 클래스: 삽입과 검색” 강의는 얼마나 걸리나요?

대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.

이 DSA Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?

네. 모든 DSA Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.

이 강의의 모든 강의

  1. TrieNode 클래스: 삽입과 검색
  2. 접두사 검색과 Starts-With
  3. 트라이에서 와일드카드와 정규식 검색
  4. 단어 검색 II: 트라이와 격자 백트래킹
← DSA Interview Prep(으)로 돌아가기