본문 바로가기

알고리즘90

트라이(Trie) 트라이의 개념은 쉽지만 글로 쓰긴 너무 길다. 까먹었을 때 이문제만 한번 다시 풀어보면 기억 날 것. https://www.acmicpc.net/problem/14425 #include #include using namespace std; const int MAX = 1e4 + 4; struct Trie { Trie* next[26]; bool term; Trie() { term = false; for (int i = 0; i < 26; i++) next[i] = NULL; } ~Trie() { for (int i = 0; i < 26; i++) if (next[i]) delete next[i]; } void insert(char* key) { if (*key == NULL) { term = true; .. 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.
codeforces #612 div2 D - Numbers on Tree (그래프, 수학, 구현) https://codeforces.com/contest/1287/problem/D 실패할 조건을 찾은데서 그친 문제. 시험볼 당시엔 좀만 보면 풀 수 있을 것 같다고 생각했지만, 꽤 오래 생각해봐도 못풀었다. 최대크기 2000의 트리가 주어진다. 각 정점마다 a[i]값을 갖는다. (이 값은 주어지지 않는다. 찾아내야 함) 이 때, 각 정점이 루트가되는 서브트리에서 현재 정점의 a값보다 작은 a값을 갖는 정점들의 수를 c값이 주어질때 가능한 a배열을 구해라. 위->아래, 왼쪽->오른쪽 순서대로 각 정점 번호가 1,2,3,4,5이다. (오른쪽 리프노드가 5번정점이다.) 크게 쓰인 수가 a값이고 괄호 안의 값이 c값이다. 1. 실패조건 각 정점을 루트로 하는 서브트리의 크기를 sz[i]라고 하자. 그러면 c[.. 2020. 1. 7.
그래프 크기 구하기 int sz[MAX]; //따로 초기화 해둘 필요 없음 bool vst[MAX]; void dfs(int curr) { vst[curr] = true; sz[curr] = 1; for (int next : adj[curr]) { if (!vst[next]) { dfs(next); //빠져나오면 curr의 next방향 서브트리의 sz모두 초기화 sz[curr] += sz[next]; } } } * 메인함수에서 dfs(rootNode)로 수행해야 모든 정점에 대해 구할 수 있음 * 양방향/단방향(부모->자식) 간선을 사용한 트리 모두에 대해 사용 가능 bool vst[MAX]; int dfs(int curr){ vst[curr]=true; int ccnt=1; for(int next: adj[curr]){ .. 2020. 1. 7.

티스토리툴바