목록Algorithm (428)
Mini
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..
백준 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 * 문..
[맞음] 백준 4811 알약 c++ // 재귀dp, 경우의수는 +
https://www.acmicpc.net/problem/4811 1.의사코드1. 알약을 1개꺼낸 경우 vs 반개꺼낸경우 계속 2분탐색이다.2. 완탐? -> 2^30 -> 불가 -> dp?3. 상태 : 큰알약갯수, 작은알약갯수 : 그때의 경우의수4. 경우의수는 기저사례 -> return 1, 후 +하면 된다.아래 그림과 같이 1이 리턴되고 거꾸로 타고오면서 그런 경우의 수가 모두 더해진다. 2. 전체코드#include using namespace std;typedef long long ll;ll dp[34][34];//큰알약남은갯수, 반알약남은갯수 : 그상태일때, 경우의수ll dfs(int a, int b) { if (a==0 && b==0) return 1; if (dp[a][b] != -1..
[틀림] 백준 1103 게임 c++ // 경우의수 dp, 사이클검사방법, 경로별 연결된 노드갯수 세는법
https://www.acmicpc.net/problem/1103 1. 사이클검사방법1. 방문한 좌표를 재방문했으면, 사이클이 있는것이다!! 2.중앙의 y,x에서 출발한경우, vis[y][x]=1 걸고들어간다탐색하면서 봤는데 vis[y][x]=1 이면, 빨간색경로로 갔다온것이다, 싸이클이 있는것임.이후, 원복을 해줘야함!원복안하는경우 : 우측의 2가 vis되있고, 다른경로(빨간경로)에서 2를 방문하면 사이클이 있는것으로 판단해버린다... 3. 의사코드if(visited) -1출력, 종료 visited = 1;상하좌우 탐색visited = 0; 2. 시행착오1. -1검사과정에서 상하좌우 같은수가 있으면 -1을 리턴하도록 했는데 이경우는1 11 1 에서는 먹히지만3 5 5 25 5 5 52 5 5 3 에서..