접두사 조회를 위한 트라이
단어 접두사를 빠르게 저장하고 조회합니다
접두사 조회를 위한 트라이은(는) CoddyKit의 무료 Competitive Programming Academy 강의입니다. 이것은 4개 중 4번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Competitive Programming Academy 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Competitive Programming Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
단어를 똑똑하게 저장하기
트라이는 공통 접두사를 공유하여 단어를 저장하는 트리입니다. 접두사 관련 질의를 매우 빠르게 처리할 수 있습니다. 🌳
그냥 집합을 쓰면 안 될까요
집합은 완전한 단어를 조회할 수 있지만, 트라이는 어떤 단어가 pre로 시작하는지와 같은 접두사 질의에도 답할 수 있습니다.
노드와 간선
각 노드는 어떤 단어 안의 한 위치를 나타내며, 각 간선에는 루트에서 이어지는 경로의 문자가 표시됩니다.
딕셔너리로 자식 관리하기
Python에서는 문자를 자식 노드에 대응시키는 딕셔너리를 노드로 사용하는 방법이 가장 간단합니다. 깔끔하고 유연합니다.
root = {}단어 삽입하기
삽입할 때는 문자를 하나씩 따라가며, 없는 자식이 나오면 새로 만듭니다.
node = root
for c in word:
node = node.setdefault(c, {})단어 끝 표시하기
삽입이 끝나면 끝 플래그를 설정하여 완전한 단어와 단순한 접두사를 구분할 수 있게 합니다.
node['#'] = True완전한 단어 검색하기
검색할 때는 문자를 따라갑니다. 어느 한 단계라도 없으면 해당 단어가 존재하지 않는 것입니다. 그다음 끝 플래그를 확인합니다.
for c in word:
if c not in node:
return False
node = node[c]접두사 확인하기
접두사 질의도 같은 방식으로 따라가지만, 끝 플래그 확인은 생략합니다. 마지막 노드까지 도달하면 해당 접두사가 존재합니다.
시간 복잡도
삽입과 조회의 비용은 저장한 단어 수와 관계없이 단어 길이인 O(L)입니다. 중요한 것은 길이입니다.
접두사별 단어 수 세기
각 노드에 개수를 저장하면 특정 접두사를 공유하는 저장된 단어가 몇 개인지 즉시 확인할 수 있습니다.
트라이가 유용한 곳
트라이는 자동 완성, 사전 확인, 비트에 대한 XOR 최댓값 문제에 활용됩니다. 대회 문자열 문제의 기본 도구입니다.
빠른 확인
트라이 조회에 실제로 드는 비용이 무엇인지 확인하세요.
복습: 트라이 마무리
이제 트라이를 만들고, O(L)에 삽입과 검색을 수행하며, 접두사와 개수 질의에 빠르게 답할 수 있습니다. 🌟
자주 묻는 질문
“접두사 조회를 위한 트라이” 강의는 무료인가요?
네 — “접두사 조회를 위한 트라이” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Competitive Programming Academy 강의 전체를 잠금 해제할 수 있습니다. Competitive Programming Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
“접두사 조회를 위한 트라이”에서 뭘 배우나요?
단어 접두사를 빠르게 저장하고 조회합니다 브라우저에서 직접 실행하는 실습 코드로 Competitive Programming Academy을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Competitive Programming Academy을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Competitive Programming Academy은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 4번째 강의입니다.
“접두사 조회를 위한 트라이” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Competitive Programming Academy 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Competitive Programming Academy 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- KMP 접두사 함수
- 다항식 문자열 해싱
- 패턴 검색을 위한 Z 함수
- 접두사 조회를 위한 트라이