dh_0e

조합론의 포함 배제의 원리를 사용하여 포카드가 나올 경우의 수를 구하는 문제dp[N][K] = N장의 카드를 뽑을 때, K개의 포카드 세트가 나올 수 있는 경우의 수를 저장하는 형식으로 1~N까지 차례로 구하며 dp로 풀 수 있을 것 같아서 5시간 동안 점화식을 찾았다... 결론적으로 이 전의 경우의 수는 관계 XN개의 카드를 뽑을 때, K개의 포카드 세트가 나왔다고 고정한 뒤, 나올 수 있는 경우의 수를 구한다.식: $cmp = {_{13}C_K} + {_{(52 - k \times 4)}C_{(N - K \times 4)}}$K를 1~N/4까지 구해준 다음, 포함 배제의 원리에 의해서 홀수번째는 더해주고, 짝수번째는 빼주면 N개의 카드를 뽑을 때 포카드가 나올 경우의 수를 구할 수 있다. ex) N이..

개미굴에서 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; i insert(key + 1)..

자료구조 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", ..