본문 바로가기

알고리즘/백준 & swacademy108

BOJ 5052 - 전화번호 목록 (Trie) https://www.acmicpc.net/problem/5052 트라이 기본문제. trie구조체의 find함수를 변형해서 풀면 된다. 트라이에 문자열들이 들어있을 때, 어떤 문자열이 다음 노드를 가지면서 term=true라면 NO를, 아니면 YES를 출력하는 문제. 1.트라이 구조를 하나 만들어 둔다. Trie* root = new Trie(); 2. find를 변형한 isConsistent를 짠다. bool isConsistent(char* key) { if (*key == 0) return 1; if (term) return 0; int c = *key - '0'; return next[c]->isConsistent(key + 1); } 무사히 끝까지 탐색했다면 consistent한 전화번호부이다... 2020. 1. 9.
BOJ 3176 - 도로 네트워크 (LCA) https://www.acmicpc.net/problem/3176 유독 LCA 코드를 짤 때 오타를 많이 내는것 같다. 최대크기 1e5인 간선 가중치가 있는 트리가 주어질 때, 1e5개의 쿼리에 답하는 문제. 쿼리 u, v : 정점u,v 사이의 경로 중 간선의 최소값과 최대값을 출력. u,v사이의 경로는 유일하다. 쿼리에 log(n)만에 답해야 한다. lca(u,v) 에서 u,v를 올려줄 때 그 과정을 따라가면서 간선 가중치 최소, 최대값(mn,mx)를 갱신할 것이기 때문에 depth를 이용하는 코드를 사용할 것이다. lca알고리즘을 다시 떠올려보자. u,v중 깊이가 더 깊은 정점을 u라고 강제하고, 1. u의 깊이를 v의 깊이에 맞춰 올려준다. 2. 같아진 u,v 깊이를 lca 직전까지 끌어올려준다. .. 2020. 1. 9.
BOJ 1086 - 박성원 (dp, bit set) https://www.acmicpc.net/problem/1086 비트셋을 이용한 어려운 dp 수가 최대 15개 주어질 때, 이 수를 모두 사용한 순열을 순서대로 이어붙인 숫자 중 k(최대100)로 나눠떨어지는 것의 개수를 이용해서 확률을 구하라. dp[i][j] : i(집합) 골랐을 때 나머지가 j인 것의 수. 초기값은 0으로 한다. (단, dp[0][0] = 1) 최종적으로 dp[(1> k; for (int i = 0; i < n; i++) { for (int j = 0; j < len[i]; j++) { a[i] = a[i] * 10 + (num[i][j] - '0'); a[i] %= k; } } vector ten(51); //10의 i승의 k 모듈러값 ten[0] = 1; for (int i =.. 2020. 1. 5.
BOJ 11779 - 최소비용 구하기 2 (다익스트라, 최단경로) https://www.acmicpc.net/problem/11779 다익스트라로 시작점->도착점의 최소비용을 구하고 그 경로중 아무거나 하나 출력하는 문제. 1. 일반적인풀이: 최단경로가 갱신될때 마다 prev[next] = curr을 해준 후에 아래와 같은 방법으로 출력해준다. stack st; int x = en; while(x!=-1){ st.push(x); x = prev[x]; } cout m; fill(d, d + MAX, INF); for (int i = 0,u,v,w; i > u >> v >> w; adj[u].push_back({ v,w }); radj[v].push_back({ u,w }); } cin >> st >> en; priority_queue pq.. 2020. 1. 5.

티스토리툴바