dh_0e

전설 (백준 19585번) 총 13번의 오답을 받으며 오랜만에 머리 터질 정도로 시간 복잡도, 공간 복잡도 둘 다 생각하게 하는 문제였다. 풀이 과정Trie 자체를 최적화(재귀 >> 동적으로)하여 시간을 줄이면서, 동시에 Trie와 unordered_set을 함께 사용해서 시간, 메모리 둘 다 잡아 AC를 받을 수 있다. Trie를 잘 구현하여 최적화하고 set만 적절하게 사용하면 쉽게 풀리는 문제인데, 그 과정까지 시행 착오가 필요하다. 메모리 초과 코드 (Double Trie)#include#include#include#include#includeusing namespace std;stack st;struct Trie { bool finish; Trie* next[26]; Trie() :finish(..

휴대폰 자판 (백준 5670번) 개미굴에서 EOF, 소수점 처리가 포함된 변형 문제while (cin >> n)로 EOF 처리, 소수점 처리 잘 해주고 Trie에 size라는 변수, find 함수에 적당한 식을 추가하면 쉽게 해결할 수있음메모리 초과가 났지만 소멸자가 제대로 작동하지 않았음 >> 소멸자 잘 작동하게 수정하니 바로 해결됨 #include#include#includeusing namespace std;char d[100001][81];struct Trie { bool finish; int size; Trie* next[26]; Trie() :finish(false),size(0) { memset(next, 0, sizeof(next)); } ~Trie() { for (int i = 0;..

개미굴 (백준 14725번) 자료구조 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 inser..

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

전화번호 목록 (백준 5052번) 자료구조 트라이(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(){ ..