알고리즘225 log2(n)값 구하기 k = log2(n)이라고 할때 floor(k)값을 구하는 로직 int k = 1; for (k = 1; (1 2020. 1. 8. 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. 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. 이전 1 ··· 27 28 29 30 31 32 33 ··· 57 다음
