트라이에서 와일드카드와 정규식 검색
해당 깊이의 모든 자식으로 탐색을 확장해 '.' 와일드카드 일치를 지원하고, 단어 추가 및 검색 자료 구조 설계 문제를 해결합니다.
트라이에서 와일드카드와 정규식 검색은(는) CoddyKit의 무료 DSA Interview Prep 강의입니다. 이것은 4개 중 3번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 DSA Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
와일드카드 search 문제
표준 트라이 search는 정확히 일치하는 문자를 처리합니다. 와일드카드 search에서는 임의의 단일 문자와 일치하는 특수 문자 '.'를 추가합니다. search 중 '.'를 만나면 특정 자식 하나를 따라가는 대신 모든 자식을 시도해야 합니다. 이것이 바로 LeetCode 211의 '단어 자료 구조 추가 및 검색 설계' 문제의 핵심 아이디어입니다. 각 '.'는 해당 수준의 자식 수만큼 search 경로를 늘립니다.
재귀적 와일드카드 search
재귀 DFS 도우미를 사용하여 와일드카드 search를 구현합니다. 패턴의 각 문자에 대해 리터럴 문자라면 특정 자식을 따라가고, 해당 자식이 없으면 거짓을 반환합니다. '.'라면 모든 자식으로 재귀 호출을 수행하고 그중 하나라도 성공하면 참을 반환합니다. 패턴이 끝나면 node.is_end를 반환합니다.
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class WordDictionary:
def __init__(self):
self.root = TrieNode()
def addWord(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):
def dfs(node, i):
if i == len(word):
return node.is_end
c = word[i]
if c == '.':
return any(dfs(child, i+1) for child in node.children.values())
if c not in node.children:
return False
return dfs(node.children[c], i+1)
return dfs(self.root, 0)
wd = WordDictionary()
wd.addWord('bad')
wd.addWord('dad')
wd.addWord('mad')
print(wd.search('.ad')) # True
print(wd.search('b..')) # True
print(wd.search('pad')) # False분기 확장에 조기 종료 함수를 사용하는 이유
'.'를 만나면 any(dfs(child, i+1) for child in node.children.values())를 호출합니다. any() 생성기는 단락 평가를 수행하므로 자식 하나가 True를 반환하는 즉시 중단됩니다. 따라서 불필요한 탐색을 피할 수 있습니다. 최악의 경우(패턴이 모두 '.'인 경우)에는 모든 경로를 탐색하므로 복잡도는 점의 개수가 k일 때 O(26^k)입니다. 따라서 큰 트라이에서는 '....'와 같은 패턴의 처리 비용이 커집니다.
큐를 사용하는 반복적 와일드카드 search
반복적 접근법에서는 (node, index) 쌍을 담은 큐를 사용합니다. (root, 0)에서 시작합니다. 각 쌍에 대해 index == len(word)이고 node.is_end가 참이면 True를 반환합니다. 그렇지 않으면 현재 문자를 처리합니다. '.'이면 모든 자식을 큐에 넣고, 리터럴 문자이면 일치하는 자식만 큐에 넣습니다. 이는 본질적으로 트라이 경로에 대한 BFS입니다.
from collections import deque
def search_iterative(root, word):
queue = deque([(root, 0)])
while queue:
node, i = queue.popleft()
if i == len(word):
if node.is_end:
return True
continue
c = word[i]
if c == '.':
for child in node.children.values():
queue.append((child, i+1))
elif c in node.children:
queue.append((node.children[c], i+1))
return False
print('Iterative BFS-based wildcard search')와일드카드 search의 복잡도 분석
와일드카드가 없는 패턴에서 search의 복잡도는 O(m)입니다. 와일드카드가 k개인 패턴의 최악의 경우는 O(26^k × m)으로, 와일드카드 개수에 대해 지수적으로 증가합니다. 실제로는 와일드카드가 드물고 트라이의 깊이도 얕은 경우가 많으므로 성능은 허용할 만합니다. 와일드카드만으로 이루어진 패턴(예: 길이가 k인 모든 단어와 일치하는 패턴)은 트라이 전체를 순회하는 형태로 퇴화합니다.
단일 문자 와일드카드를 넘어선 정규식 search
완전한 정규식(예: 0개 이상의 문자를 일치시키는 '*')으로 확장하려면 다른 처리가 필요합니다. '*'는 임의의 접미사와 일치할 수 있으므로 이를 만나면 현재 노드에서 시작하는 모든 트라이 경로를 시도해야 합니다. 트라이에서 실제 정규식 일치를 구현하는 것은 복잡하며, 일반적으로 NFA/DFA 구성에 맡깁니다. 면접에서는 단일 문자 와일드카드('.')가 표준 패턴입니다.
글로브 패턴 일치
'?'(임의의 단일 문자)와 '*'(빈 문자열을 포함한 임의의 문자열)에 대한 글로브 일치는 DP로 구현할 수 있습니다. 트라이에서 구현한다면 '?'는 '.'와 같은 단일 수준 분기 확장에 대응하고, '*'는 여러 수준에 걸친 DFS에 대응합니다. 결합된 DP 접근법에서는 dp[i][j]가 pattern[0..i]가 string[0..j]와 일치하면 True라는 뜻입니다. 면접관은 일반적으로 구현할 변형을 지정합니다.
실전 적용: IP 주소 라우팅
와일드카드 트라이는 '*'가 접두사 와일드카드로 작동하는 IP 라우팅 테이블에서 사용됩니다. 라우터는 '192.168.*'와 같은 경로 접두사를 저장하고 들어오는 주소와 일치시킵니다. 최장 접두사 일치(가장 구체적인 경로가 선택됨)는 트라이를 가능한 한 깊이 순회한 뒤 마지막으로 확인한 일치 항목을 사용하는 방식으로 구현합니다. 이는 트라이의 접두사 및 와일드카드 연산을 실제로 적용한 사례입니다.
최적화: 도달 불가능한 분기 가지치기
트라이 노드에 자식이 없고(리프 노드) 종료 표시가 거짓이면 해당 노드에 도달하는 모든 search는 거짓을 반환합니다. 와일드카드 search 중 재귀 호출 전에 이러한 막다른 노드를 건너뛰면 불필요한 호출을 줄일 수 있습니다. 각 노드에 하위 트리의 전체 단어 수를 유지하면, 남은 패턴 길이 조건에 맞는 단어가 없을 때 하위 트리 전체를 건너뛸 수 있습니다.
전체 WordDictionary 클래스(면접 대비)
삽입과 점 와일드카드 search를 하나의 클래스에 결합한 깔끔한 면접 대비용 WordDictionary입니다. LeetCode 211에서 요구하는 구현과 정확히 같습니다. 단락 평가를 사용하는 재귀 search는 간결하며 면접관에게 분기 확장 로직을 명확하게 보여 줍니다.
class WordDictionary:
def __init__(self):
self.root = {}
def addWord(self, word):
node = self.root
for c in word:
node = node.setdefault(c, {})
node['#'] = True
def search(self, word):
def dfs(node, i):
if i == len(word):
return '#' in node
if word[i] == '.':
return any(dfs(v, i+1) for k, v in node.items() if k != '#')
nxt = node.get(word[i])
return dfs(nxt, i+1) if nxt is not None else False
return dfs(self.root, 0)
wd = WordDictionary()
for w in ['at','and','an','add']:
wd.addWord(w)
print(wd.search('a.')) # True (at, an)
print(wd.search('.nd')) # True (and)
print(wd.search('...')) # True (and, add)
print(wd.search('x.')) # Falsesetdefault를 사용한 간결한 트라이
dict.setdefault(key, default)는 key가 있으면 해당 값을 반환하고, 없으면 default를 삽입한 뒤 그 값을 반환합니다. 삽입 과정에서 node.setdefault(c, {})를 사용하면 if-else 확인을 없앨 수 있습니다. 자식 딕셔너리가 없으면 생성하고, 어느 경우든 해당 딕셔너리를 반환하기 때문입니다. 따라서 삽입을 한 줄 순회로 작성할 수 있습니다. for c in word: node = node.setdefault(c, {}). 간결하고 파이썬다운 방식입니다.
빠른 확인
이 단원에서 배운 자료 구조 & 알고리즘 — 코딩 면접 준비 개념을 제대로 이해했는지 확인해 보세요.
단원 요약
이 단원에서는 와일드카드 '.'가 일치하는 위치에서 재귀 DFS를 사용해 모든 자식으로 분기 확장해야 한다는 점, 생성기와 함께 단락 평가 함수를 사용하면 조기 종료가 가능하다는 점, 그리고 setdefault를 사용하면 트라이 삽입을 간결한 한 줄로 작성할 수 있다는 점을 배웠습니다. 다음에는 트라이와 백트래킹을 결합하여 2차원 보드에서 여러 단어를 동시에 찾는 단어 검색 II를 해결합니다.
자주 묻는 질문
“트라이에서 와일드카드와 정규식 검색” 강의는 무료인가요?
네 — “트라이에서 와일드카드와 정규식 검색” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 DSA Interview Prep 강의 전체를 잠금 해제할 수 있습니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“트라이에서 와일드카드와 정규식 검색”에서 뭘 배우나요?
해당 깊이의 모든 자식으로 탐색을 확장해 '.' 와일드카드 일치를 지원하고, 단어 추가 및 검색 자료 구조 설계 문제를 해결합니다. 브라우저에서 직접 실행하는 실습 코드로 DSA Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
DSA Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 DSA Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 3번째 강의입니다.
“트라이에서 와일드카드와 정규식 검색” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 DSA Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 DSA Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- TrieNode 클래스: 삽입과 검색
- 접두사 검색과 Starts-With
- 트라이에서 와일드카드와 정규식 검색
- 단어 검색 II: 트라이와 격자 백트래킹