트라이(Trie)

이진 탐색 트리와 달리 트리의 어떤 노드도 그 노드 자체와 연관된 키는 저장하지 않는다. 노드의 모든 자손은 노드에 연관된 문자열의 공통 접두사를 공유한다. 따라서 모든 노드가 꼭 키와 연결되지는 않는다. 어떤 노드는 word의 원소에 대한 정보를 담고 있는데 이는 해당 노드까지 탐색하게 되면 탐색 과정에서 등장한 알파벳으로 이뤄진 단어가 현재 트라이에 존재한다는 의미를 나타낸다. 시간 복잡...

문자열자료구조알고리즘트라이백준문자열

[알고리즘] 트라이 개념 및 구현하기

문자열을 저장하고 탐색하기 위한 트리모양 자료구조 자동완성, 사전찾기에 응용됩니다 문자열 탐색에 최적화된 자료구조 입니다 문자마다 노드를 만들어야하기 때문에 저장공간이 많이 필요합니다 탐색 시간복잡도는 문자열의 길이 L에 대해 O(L)만큼만 걸립니다 트라이를 구현할 때 몇가지 규칙이 있습니다. root 노드는 항상 비어있습니다 간선은 추가될 문자입니다 각 노드는 이전 정점의 값 + 간선에 추...

트라이알고리즘알고리즘

[백준] 5670번 휴대폰 자판

타이핑 할 때 자동으로 입력 가능한 글자가 있으면 자동으로 입력해주는 기능 개발 사전 단어 리스트가 주어짐 평균 타이핑 횟수 출력 트라이 구현 Node 클래스 구현 후 root 노드에 계속해서 삽입 BFS로 탐색하면서 카운트 현재 루트가 아니면서, 마지막 철자가 아니면서, 자식 노드가 하나일 때 level 유지 트라이 자료구조를 연습하기 위해 풀어봤다 EOF도 처리해야한다...

트라이트라이

[Python] 백준 4358 - 생태학 문제 풀이

BOJ 4358번 생태학 Python 문제 풀이 분류: Trie (트라이) Trie 자료구조를 구현하여 풀이하였다. 종 이름의 각 글자 별로 트라이 구조에 저장하고, 마지막 글자에는 cnt 속성에 1씩 더한다. 이렇게 하면 트라이를 탐색 할 때, 종 이름 끝 지점에서 몇 마리가 존재하는지 알 수 있다. defaultdict를 이용하여 각 종의 수를 세고, 결과를 출력한다....

Trie트라이Trie

[C++] 백준 5052번: 전화번호 목록

문제 링크 문제 요약 주어진 전화 번호 중에 어떠한 전화번호가 다른 전화번호의 접두어가 되는 경우가 있는지 판별해야 한다. 접근 방법 트라이를 이용해서 풀었습니다. 먼저 입력으로 주어진 전화번호들을 모두 트라이에 집어 넣습니다. 그 다음에 각 전화번호로 순서대로 트라이에서 탐색을 합니다. 만약에 전화번호의 맨 마지막 번호에 해당하는 노드에 도달했을때, 자식 노드가 존재한다면 해당 전화번호는 ...

트리백준자료 구조문자열트라이문자열