너와 나의 스토리

문제: https://programmers.co.kr/learn/courses/30/lessons/60060 문제 풀이: 단순히 trie를 짠 다음에 queries[i]에서 '?'가 나오면 해당 trie 노드에서 갈라지는 모든 곳으로 가도록 구현했더니 효율성 테스트에서 시간 초과가 났다. -> 정적 트라이로 풀어도 ㅠㅠ 해설을 보니 words를 trie에 insert할 때, 원래 문자열들로 만드는 트라이 하나, 뒤집은 문자열로 만드는 트라이 하나, 이렇게 두 개 만들어 각각 넣어주면 된다고 한다. 그리고 문자열 길이마다 트라이를 미리 만들어 놓고, 길이에 맞는 트라이에 삽입함으로써 ?를 만났을 때 바로 가능한 문자들의 개수를 리턴해주고 끝나면 된다. 가능한 문자들의 개수는 처음 words를 입력할 때, ..

문제: https://www.acmicpc.net/problem/5446 문제 풀이: 1. 지워야 할 파일들을 trie에 insert 2. 지우면 안 될 파일들이 이름이 trie에 존재하는 것들과 겹치는 부분을 체크 (no=true) 3. 전체 trie 순환하면서 no가 아닌 부분에 도달하면 res++하고 그 라인은 더 이상 보지 않음 * [rm *]이 가능하려면 root에 존재하는 모든 next에 대해 no 플래그가 off 되어 있어야 한다. 이를 체크하기 위해 2번 작업을 수행하다 no를 한 번이라도 체크하게 되면 root->no=true가 되게 하였다. root->no가 false라면 rm *이 가능하므로 답은 1이 된다. 소스코드: #include #define QSIZE 63002 using n..

문제: https://www.acmicpc.net/problem/10256 문제 풀이: 아호코라식 알고리즘을 이용한다. 1. 주어진 마커를 뒤집어서 나올 수 있는 모든 문자열을 trie에 넣는다 2. DNA 문자열을 root부터 대입 시키면서 마커의 끝을 만나면 res에 더해준다 소스 코드: #include #include #include #include #include using namespace std; int tc, n, m; char str1[1000002], str2[102]; struct trie { trie *next[4]; trie *fail; int finish; trie() { fill(next, next + 4, nullptr); finish = 0; } ~trie() { for (i..

문제: https://www.acmicpc.net/problem/5052 동적 할당 방식 #include using namespace std; const int TrieNode = 10; struct Trie { Trie *next[TrieNode]; bool finish; bool nextChild; Trie() { fill(next, next + TrieNode, nullptr); finish = nextChild = false; } ~Trie() { for (int i = 0; i < TrieNode; i++) { if (next[i]) delete next[i]; } } bool insert(const char* key) { if (*key == '\0') { finish = true; retur..

문제: https://www.acmicpc.net/problem/9202 문제 설명: 상하좌우, 대각선 총 8개의 방향으로 이어지는 단어가 사전에 존재하는 단어를 찾아 해당 단어의 길이별로 점수를 매긴다 각 단어에 속하는 글자 수 1,2 글자 -> 점수는 0점, but 찾은 단어로 카운트는 해야함 3,4 글자 -> 점수: 1점 5 글자 -> 점수: 2점 6 글자 -> 점수: 3점 7글자 -> 점수: 5점 8글자 -> 점수: 11점 문제 풀이: 1. 사전에 들어있는 단어를 입력 받을 때, trie에 삽입한다. boggle 보드에서 abcdef라는 조합이 가능하고 사전에 abcd와 abcde라는 단어가 있을 때 우리는 두 단어 모둘 카운트를 해야한다. 그러므로 트라이에 해당 위치에서 자식이 있는지를 판별하는..

문제: https://www.acmicpc.net/problem/5670 Ries님의 블로그를 참고하여 문제를 풀었다 마지막에 생성한 trie를 할당 해제(delete root)를 안해줘서 메모리 초과가 났다 ㅠㅠ 입력 받을 때, while (scanf("%d", &n))로만 하면 출력 초과가 난다. -> while (scanf("%d", &n)>0)로 바꿔주면 됨 소스 코드: ...더보기 #define _CRT_SECURE_NO_WARNINGS #include using namespace std; int n; struct trie { trie* next[26]; int word, branch; trie() { fill(next, next + 26, nullptr); word = branch = 0; }..

문제: https://www.acmicpc.net/problem/14425 문제 설명: 1. n과 m을 입력 받음 2. n개의 문자열을 입력 받음(형광펜) -> 집합 S 3. m개의 문자열을 입력 받음 이 때 입력 받은 문자열이 집합 S에 있으면 cnt++ * baekjoon은 집합 S에 포함되는거 아님 baekjoononlinejudge처럼 완전히 일치하는 것만 포함되는 걸로 취급 문제 풀이: Trie 메모리 제한이 1536 MB로 넉넉하므로 trie로 풀어보았다. insert함수로 trie를 만들고 check함수로 포함되는지 확인 했다. check함수에서 현재 문자열이 새로운 길로 가려고 하면 S에 포함되지 않는 것이므로 -> false 리턴 현재 문자열을 끝까지 다 봤고 S에 속하는 문자열도 이 곳..