분류 전체보기

백준 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이면 유일값이므로 그..

백준 21276 계보복원가호석 c++ // 위상정렬, 조상찾기주의점, 문자열을 idx로 바꿔서 풀어라

https://www.acmicpc.net/problem/21276 1. 문자열을 idx로 바꿔서 풀어라1. map m을 두고 sort 후m["철수"] = 0 , m["석열"]=1 ... 이런식으로 할당하면 된다.2. 이래야 실수를 줄이고 디버깅, 복잡도등 이점이 많다.. 2. 조상찾기주의점석호 철수(조상) 일때,석호 그래야 철수의 indegree가 0이됨.* 위상정렬의 기본 idea가 indegree가 0인점을 제거해 나간다는 점을 꼭 생각할것!! 3. 의사코드1. 문자열을 idx로 바꿈2. 입력만 문자열일뿐 숫자 위상정렬과 같이 생각하면 쉽다.자료구조가 숫자 그자체에서 해당 idx로 바뀌었을 뿐이다.vector adj[1001]; //i노드의 인접리스트들의 idxvector child[1001]; /..

백준 2623 음악프로그램 c++ // 위상정렬, 사이클 검사방법

https://www.acmicpc.net/problem/2623 1. 사이클 검사방법결론 : 큐를 탐색하면서 , 차수가 0인애를 result에 담고, result.size가 n이아니면 사이클이 있는것임!이유 : 위와 같을때, a가 큐에들어가려면 c가 없어지면서 deg[a]-1 해줘야 되고c가 큐에 들어가려면 b가없어지면서 deg[c]-1 해줘야 되는데a,b,c는 서로가 없어져야 큐에들어갈수 있음 -> 그런데 데드락처럼 큐에 들어갈수없는 존재들이다.따라서 사이클이 있는 a,b,c는 정답에 들어가지 않음 -> result.size()가 4(n)가 아닌 1이 되어있음 2. 전체코드#include using namespace std;typedef long long ll;vector adj[10001]; //i..

백준 2252 줄세우기 c++ // 위상정렬

https://www.acmicpc.net/problem/2252 1. 위상정렬주로 수강신청시 선수과목, 줄세우기 등순서를 정해야하는 문제일때, 사용하면 된다. 2. 의사코드1. degree : 나한테 들어오는 화살표의 갯수 // a->b2. degree가 0이다 -> 맨앞에 와도 ok -> 큐에넣기3. 맨앞에 오고, 연결노드들의 차수 -1 해주기.4. 연결노드들의 차수가 0이다? -> 큐에넣기5. 큐가빌때까지 반복 3. 전체코드#include using namespace std;typedef long long ll;vector adj[32001]; //i노드의 인접노드들int deg[32001]; // i노드의 차수int n, m;int main() { ios_base::sync_with_stdi..

백준 2042 구간합구하기 c++ // 펜윅트리 구현방법

https://www.acmicpc.net/problem/2042 1. 구간합배열 vs 펜윅트리수정이 많다면 펜윅트리를 사용해야한다! 2. 펜윅트리 구현방법1. 삽입 : (idx, diff)a[9] : 6을 9로 바꿈 -> 차이인 "3" 만큼을 내려가면서(부모노드에) 갱신시켜줘야함! //원본값 9가 아님에 주의!부모노드의 idx는 어케얻음? -> 9(1001) -> 10(1010) -> 12(1100) -> 16(10000)즉, 본인 idx에서 최하위 비트(1)을 더해주면 부모노드의 idx가 나온다! //1001(9) + 0001 == 1010(10) ... 2. 누적합구하기퍼랭이들을 더해야하는데7에서 시작해서 다음퍼랭이 idx를 얻어내면된다.0111(7) -> 0110(6)->0100(4)즉, 최하의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..