트라이3 BOJ 17306 - 전쟁 중의 삶 (트라이, 완전이진트리) https://www.acmicpc.net/problem/17306 무한완전 이진트리가 주어지고 루트(1)부터 각 정점에 순서대로 번호가 매겨진다. 최대 25e4개의 정짐의 번호(2^50보다 작음)가 주어진다. 정점간의 경로 상에 포함되는 모든 정점의 수를 구하라 각 정점의 번호를 2진수로 나타내면 1에서부터 그 정점까지의 경로를 트라이로 표현할 수 있다. 각 정점마다 1에서부터 경로 상의 최대 정점 수는 50개이므로 트라이의 총 노드의 수는 최대 50n개이다. 트라이의 각 노드 u마다 u를 루트로하는 서브트리에 포함된 정점의 수(term==1인 정점의 수)를 d[u]라고 할 때, d[u]가 1이상 n미만인 경우 u는 경로상에 반드시 포함된다. #include #define FAST ios_base::s.. 2020. 6. 10. BOJ 5670 - 새로운 자판 (Trie) https://www.acmicpc.net/problem/5670 이정도까진 풀수 있어야 한다. 자동완성 기능이 있는 자판이 있다. abczx abcxx abcyy 가 등록되어 있다고 가정할 때, a를 자판에 누르는 순간 abc가 자동완성된다. 등록되어있는 단어들을 모두 입력하는데 자판을 누르는 회수의 총합을 전체 등록된 문자의 수로 나눈 것을 구하자. 등록된 문자를 모두 find하면서 각 문자를 쓰는데 눌러야하는 자판 횟수를 ll cntKey(char* key, bool isRoot, ll cnt) 라고 하자. main에서 호출, 출력하는 코드 ll sum = 0; for (int i = 0; i cntKey(w[i], 1, 0); printf("%.2lf\n".. 2020. 1. 9. 트라이(Trie) 트라이의 개념은 쉽지만 글로 쓰긴 너무 길다. 까먹었을 때 이문제만 한번 다시 풀어보면 기억 날 것. https://www.acmicpc.net/problem/14425 #include #include using namespace std; const int MAX = 1e4 + 4; struct Trie { Trie* next[26]; bool term; Trie() { term = false; for (int i = 0; i < 26; i++) next[i] = NULL; } ~Trie() { for (int i = 0; i < 26; i++) if (next[i]) delete next[i]; } void insert(char* key) { if (*key == NULL) { term = true; .. 2020. 1. 9. 이전 1 다음
