dh_0e

자료구조 Trie를 변형해서 풀 수 있는 문제map로 next에 key값으로 string, value에 Trie의 포인터 값을 저장하게끔 map을 만들어 준 후, input 데이터를 저장해준다.dfs형식의 print 함수를 적절히 만들어 next에 저장된 tree 형식의 데이터를 출력 #include#include#include#include#includeusing namespace std;struct Trie { bool finish; map next; Trie() :finish(false) {}; ~Trie() { for (auto it = next.begin(); it != next.end(); it++) delete(it->second); }; void insert(vector vec, in..

트라이(Trie)여러 개의 문자열을 효율적으로 저장, 탐색 및 삭제 할 수 있는 자료구조 Retrieval tree에서 "Trie"를 도출한 이름사전 순 정렬이 자동으로 되며, 해시 충돌이 없기 때문에 해시 테이블보다 stable함자동 완성(검색어 추천 기능), 사전 구현, 문자열 패턴 매칭 등에서 사용됨  구조트라이는 루트 노드(root node)를 가지고 있으며, 각 노드는 알파벳(혹은 문자)별로 자식 노드를 가질 수 있음finish(또는 isEndOfWord) 변수를 두어 문자열의 끝을 나타냄(root) ├── C │ ├── A │ │ ├── T (finish=true) │ │ ├── N (finish=true) 위 예제에선 "CAT"과 "CAN"이 저장되어 있으며, T와 ..

자료구조 트라이(Trie) 기초 문제로 해시 테이블을 사용해서 풀 수도 있는 문제 Trie를 문제에 맞게 구현해주면 쉽게 풀 수 있다.insert 도중 finish가 true면 일관성 Xinsert가 끝난 후 finish에 true 값을 저장하려는데 number 배열이 비어있지 않으면 일관성 X  #include#include#includeusing namespace std;struct Trie { bool finish; Trie* number[10]; Trie() :finish(false) { memset(number, 0, sizeof(number)); } ~Trie() { for (int i = 0; i insert(key + 1); }};int main(){ int t; scanf("%d", ..