접두사 검색과 Starts-With
starts_with 메서드를 추가해 삽입된 단어 중 주어진 접두사를 공유하는 단어가 있으면 true를 반환하도록 하고, 이를 사용해 자동 완성 제안을 구현합니다.
접두사 검색과 Starts-With은(는) CoddyKit의 무료 DSA Interview Prep 강의입니다. 이것은 4개 중 2번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 DSA Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
접두사 조회의 힘
Trie가 해시 맵보다 갖는 핵심 장점은 효율적인 접두사 조회입니다. 접두사 조회를 사용하면 '이 접두사로 시작하는 저장된 단어는 몇 개인가?', '이 접두사로 시작하는 저장된 단어는 모두 무엇인가?', 또는 간단히 '이 접두사로 시작하는 단어가 하나라도 존재하는가?'와 같은 질문에 답할 수 있습니다. 이러한 조회는 저장된 전체 단어 수와 관계없이 O(p)이며, 여기서 p는 접두사 길이입니다. 따라서 Trie는 autocomplete와 검색 추천에 적합합니다.
starts_with 메서드
starts_with(prefix)는 저장된 단어 중 주어진 접두사로 시작하는 단어가 하나라도 있으면 참을 반환합니다. 접두사의 각 문자를 따라 Trie를 순회합니다. 누락된 간선 없이 모든 문자를 따라갈 수 있으면 접두사가 존재하고, 해당 접두사로 시작하는 단어가 하나 이상 있다는 뜻입니다. 구현은 search와 동일하지만 순회를 끝내는 즉시 참을 반환하며 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 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
t = Trie()
for w in ['hello','help','world','word']:
t.insert(w)
print(t.starts_with('hel')) # True
print(t.starts_with('wor')) # True
print(t.starts_with('xyz')) # False접두사로 시작하는 모든 단어 찾기
autocomplete를 구현하려면 접두사의 끝 노드까지 순회한 다음, 해당 노드에서 DFS(또는 BFS)를 수행하여 그 노드에서 뻗어 나오는 모든 단어를 수집합니다. 수집한 각 접미사 앞에 접두사를 붙여 전체 단어를 복원합니다. 이 연산은 O(p + W)이며, W는 일치하는 모든 단어에 포함된 전체 문자 수입니다.
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 autocomplete(self, prefix):
node = self.root
for c in prefix:
if c not in node.children:
return []
node = node.children[c]
# DFS from prefix end node
results = []
def dfs(n, path):
if n.is_end:
results.append(prefix + path)
for char, child in n.children.items():
dfs(child, path + char)
dfs(node, '')
return results
t = Trie()
for w in ['apple','app','application','apply','apt']:
t.insert(w)
print(t.autocomplete('app')) # ['app','apple','apply','application']정렬된 autocomplete 추천 반환
정렬된 autocomplete를 구현하려면 DFS 중에 자식을 알파벳 순서로 순회합니다(sorted(node.children.items())를 순회합니다). 자식이 사전에 저장되어 있으므로 이 방식은 O(ALPHABET_SIZE × 깊이)의 추가 비용이 들지만 사전식 순서로 정렬된 결과를 보장합니다. 배열 기반 Trie에서는 인덱스 0~25가 정렬되어 있으므로 자식이 항상 알파벳 순서로 순회됩니다.
def dfs_sorted(node, prefix, results):
if node.is_end:
results.append(prefix)
for char in sorted(node.children.keys()): # alphabetical order
dfs_sorted(node.children[char], prefix + char, results)
print('Iterating children in sorted order gives lex-sorted suggestions')빈도 기준 상위 k개 autocomplete 추천
빈도 기준 상위 k개 추천을 구현하려면 각 노드에 해당 위치에서 끝나는 단어가 검색된 횟수를 저장합니다. 추천을 수집할 때는 크기가 k인 최대 힙을 사용합니다. 이렇게 하면 모든 일치 항목을 구체화하지 않고 DFS 결과 집합을 O(W)에서 O(k)로 줄일 수 있습니다. 실제 검색 엔진은 빠르고 관련성 높은 추천을 제공하기 위해 Trie의 접두사 순회와 빈도 데이터를 결합합니다.
LeetCode 208용 Trie 구현
LeetCode 208의 'Trie(접두사 트리) 구현'은 정확히 다음을 요구합니다. insert(word), 정확히 일치하는지 나타내는 불리언을 반환하는 search(word), 접두사가 일치하는지 나타내는 불리언을 반환하는 startsWith(prefix)입니다. 이것이 표준적인 Trie 구현입니다. search에는 is_end=True가 필요하고, startsWith에는 접두사 경로가 존재하기만 하면 된다는 점을 기억하세요.
class Trie:
def __init__(self):
self.root = {}
def insert(self, word):
node = self.root
for c in word:
if c not in node:
node[c] = {}
node = node[c]
node['#'] = True # '#' marks word end
def search(self, word):
node = self.root
for c in word:
if c not in node: return False
node = node[c]
return '#' in node
def startsWith(self, prefix):
node = self.root
for c in prefix:
if c not in node: return False
node = node[c]
return True
t = Trie()
t.insert('apple')
print(t.search('apple')) # True
print(t.search('app')) # False
print(t.startsWith('app')) # True'#'을 끝 표시로 사용하기(사전형 Trie)
Trie를 중첩된 사전으로 저장하고 '#'와 같은 특수 센티널 키로 단어의 끝을 표시하면 TrieNode 클래스가 필요하지 않다는 우아한 지름길을 사용할 수 있습니다. 이 방식은 간결하고 면접에 적합하지만 명시적인 TrieNode 객체를 사용하는 것보다 읽기 어렵습니다. 두 구현 모두 사용할 수 있으며, 시간 제한이 있을 때는 사전 방식이 더 빠르게 작성됩니다.
Trie를 사용한 최장 공통 접두사
문자열 목록의 최장 공통 접두사를 찾으려면 모든 문자열을 Trie에 삽입한 다음 루트에서 시작해 다음 조건이 유지되는 동안 하나뿐인 경로를 따라갑니다. (1) 현재 노드에 자식이 정확히 하나 있고, (2) is_end가 거짓입니다. 어느 한 조건이 깨지면 중단합니다. 따라간 경로가 최장 공통 접두사입니다.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
def longest_common_prefix(words):
root = TrieNode()
for word in words:
node = root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.is_end = True
prefix = []
node = root
while len(node.children) == 1 and not node.is_end:
char, node = next(iter(node.children.items()))
prefix.append(char)
return ''.join(prefix)
print(longest_common_prefix(['flower','flow','flight'])) # 'fl'
print(longest_common_prefix(['dog','racecar','car'])) # ''단어 교체 문제
단어 교체(LeetCode 648) 문제에서는 어근 단어 사전과 문장이 주어질 때, 문장의 각 단어를 사전에서 일치하는 가장 짧은 어근으로 바꿔야 합니다. 모든 어근을 Trie에 삽입합니다. 문장의 각 단어에 대해 Trie를 순회하다가 어근의 끝을 찾으면 해당 어근을 교체 결과로 반환합니다. 일치하는 어근이 없으면 원래 단어를 유지합니다. 이 방식은 무차별 대입의 O(n × m) 대신 O(전체 문자 수)에 실행됩니다.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
def replaceWords(dictionary, sentence):
root = TrieNode()
for word in dictionary:
node = root
for c in word:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.is_end = True
def find_root(word):
node = root
for i, c in enumerate(word):
if c not in node.children: break
node = node.children[c]
if node.is_end:
return word[:i+1]
return word
return ' '.join(find_root(w) for w in sentence.split())
print(replaceWords(['cat','bat','rat'], 'the cattle was rattled by the battery'))맵 합 쌍 문제
맵 합(LeetCode 677) 문제에서는 키-값 쌍을 삽입하고, 주어진 접두사를 가진 모든 키의 값 합계를 반환합니다. 각 TrieNode에 val 필드를 추가합니다. 삽입할 때는 끝까지 순회하여 값을 설정하고, 합계 조회를 수행할 때는 접두사의 끝 노드까지 순회한 후 그 아래의 모든 val 필드를 DFS로 합산합니다. 또는 삽입 중 각 노드에 누적 합계를 저장하면 O(p) 시간에 조회할 수 있습니다.
제한된 결과로 자동 완성 구현
프로덕션 자동 완성 시스템에서는 접두사와 일치하는 단어가 수천 개일 때 모든 단어를 반환하는 것이 비현실적입니다. 대신 DFS 순회 중에 크기 k의 최대 힙을 사용하여 지금까지 찾은 점수가 가장 높은 k개 단어를 유지합니다. 상위 k개 단어가 절대 포함될 수 없는 경우에는 점수 상한을 이용해 가지치기하여 DFS 분기를 일찍 중단합니다. 그러면 k개 추천을 반환할 때 질의당 O(p + k × log k)이 되어 모든 일치 항목을 수집하는 것보다 훨씬 효율적입니다.
빠른 확인
이 단원에서 배운 자료 구조 & 알고리즘 — 코딩 면접 준비 개념을 제대로 이해했는지 확인해 보세요.
단원 요약
이 단원에서는 접두사 확인 기능이 접두사 경로를 순회하고 해당 경로가 존재하면 참을 반환하므로 종료 여부를 확인할 필요가 없다는 점, 자동 완성 DFS가 접두사의 끝 노드에서 시작하여 내려가면서 문자를 append해 모든 단어를 수집한다는 점, 그리고 노드에 개수나 값을 추가하면 합계 질의와 상위 k개 추천이 가능해진다는 점을 배웠습니다. 다음에는 트라이에 와일드카드와 정규식 일치 기능을 추가합니다.
자주 묻는 질문
“접두사 검색과 Starts-With” 강의는 무료인가요?
네 — “접두사 검색과 Starts-With” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 DSA Interview Prep 강의 전체를 잠금 해제할 수 있습니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“접두사 검색과 Starts-With”에서 뭘 배우나요?
starts_with 메서드를 추가해 삽입된 단어 중 주어진 접두사를 공유하는 단어가 있으면 true를 반환하도록 하고, 이를 사용해 자동 완성 제안을 구현합니다. 브라우저에서 직접 실행하는 실습 코드로 DSA Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
DSA Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 DSA Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 2번째 강의입니다.
“접두사 검색과 Starts-With” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 DSA Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 DSA Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- TrieNode 클래스: 삽입과 검색
- 접두사 검색과 Starts-With
- 트라이에서 와일드카드와 정규식 검색
- 단어 검색 II: 트라이와 격자 백트래킹