Algorithm/트라이

리트코드 211 c++ // 트라이 와일드카드 종결, 재귀vs길이별 트라이

https://leetcode.com/problems/design-add-and-search-words-data-structure/description/?source=submission-noac1. 와일드카드가 처음, 중간, 끝에 있는경우 모두 커버하는 코드1. 삽입부분은 기존과 동일하다.2. 검색에서 재귀함수를 써야한다.bool search(const string& word, int index) const { //끝에const => 이함수에서는 클래스내부 변수 수정금지 if (index == word.size()) { //문자끝에 온경우 return isEnd; } char c = word[index]; ..

리트코드 208. Trie 구현 c++ // 트라이복습, c클래스 초기화 방법

https://leetcode.com/problems/implement-trie-prefix-tree/ 1. c클래스 초기화 방법private: int a, int arr[30]public : className() : a(0), arr() {}암기할것 2. 트라이 복습1. 자식배열을 가진다. Trie* child[26]2. 새로운 자식할당은 new Trie로 한다.자식할당시 cur->child[c-'a'] = new Trie() 암기할것 class Trie {private: int isEnd; Trie* child[26];public: Trie() : child(),isEnd(0) {} //초기화방법 암기할것 void insert(string word) { Tri..

백준 5670 c++ 휴대폰자판 // 트라이 자식수, 소수점출력방법, mx설정방법

https://www.acmicpc.net/problem/56701. mx설정방법1. 그냥 문제에 있는 단어길이의 총합을 mx로 잡으면 된다.n * 단어의 길이 -> 시간초과 난다...각 테스트 케이스마다 입력으로 주어지는 단어의 길이 총합은 최대 10^6이다. 2. 소수점출력방법 cout 하면된다. 3. 트라이 자식수(의사코드)1. insert 하면서 cnt를 +1 하면서 지나감 // cnt가 1임 -> 유일값2. 값이 -1이면, child를 +1 한다. // 자식수를 기록해놓는다.3. 삽입마지막단계에 chk배열로 단어의 끝을 표시한다.* find ( root의 자식 부터 시작하므로 ret=1부터 시작)0. !! ret+1은 다음단어를 입력받는다는 뜻이다. !!1. cnt가 1이면 유일값이므로 그..

프로그래머스 가사검색 c++ // 정석트라이, 단어 길이별 트라이, 접미사 구하는법, 한계

https://school.programmers.co.kr/learn/courses/30/lessons/60060 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr1. 정석트라이1. 노드기반 트라이 임원소 : Trie* child, cnt(만족단어갯수) 2. 야매 트라이와 비교1. cur= root(시작점) / nxt==-1 (자식없음) / nxt[cur][c - 'a']= unused++ (자식할당)2. cur=this / cur->child == nullptr / cur->child[c-'a'] = new Trie(); 3. 의사코드1. 길이를 딱 맞춰서 정..

프로그래머스 자동완성 c++ // 트라이, 자동완성 결정방법

https://school.programmers.co.kr/learn/courses/30/lessons/17685 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr1. 자동완성 결정방법1. cnt[node] 배열을 두고,2. insert하면서 지나갈때마다 cnt[node] +1 하면서 지나간다.3. cnt가 1이면, 유일한것이다. 2. 의사코드1. 모두 삽입후 이런 상태가 된다.2. cur을 내려가면서 (한글자씩 보면서) 1을 찾으면 더 들어가지말고(brak), ret를 리턴하면된다.int find(string& s){ int ret=0; int cu..

백준 5052 전화번호 목록 c++ // 트라이, 서로 접두어검사, 입력값은 모두받아야함

https://www.acmicpc.net/problem/5052 1. 의사코드1. 경우1 : 삽입단어 > 기존단어 : 단어삽입중, cur이 끝체크되있다면? -> 접두어관계이다.2. 경우2 : 삽입단어   단어삽입이 끝났는데, unused-1 와 cur위치가 다름 // new단어 삽입시 cur == unused-1 이다.ex) 위 그림에서 APP삽입시, cur=4인데, unused(18)는 저 멀리 가있다. 2. 시행착오1. !입력값은 모두받아야함!2. 문제 : 바로종료하면 ㄱㅇㄷ일듯? -> 남은 입력값이 붕떠버림 -> 예측불가해결 : flag만 갱신하고, 모든입력을 insert 해야함! if (!insert(s)) { cout  3.전체코드#include using names..

백준 5052 접두사 찾기 c++ // 트라이, 접두사검사, 포함검사

https://www.acmicpc.net/problem/14426 1. 트라이해당 문자 삽입, 삭제, 검색을 O( s.size()) 만에 가능하게 하는 알고리즘이다.주로 접두사검사, 포함검사, 자동완성기능 키워드가 있으면, 트라이 문제이다!1. 삽입2. 삭제chk[cur] 만 0으로 만들어 놓으면된다.3. 검색자식이 -1이면, false를 반환하면된다.그외에는 1 반환. -> 접두사검사chk[cur] 반환 -> 완전한 포함검사  2. 전체코드#include using namespace std;typedef long long ll;const int ROOT = 1; //1번부터 시작!int unused = 2; //다음노드 넣을 번호const int MX = 10000 * 500 + 5; // N * 문..