본문 바로가기

알고리즘/메모44

소인수 분해, 약수의 개수, 오일러 피함수 에라토스테네스 :https://suuntree.tistory.com/36?category=805933 소인수분해 자체로는 문제가 많이 나오지않지만 오일러 피함수는 알고있어야 한다. 1. 소인수분해 : O(loglogn) -> while문 수행횟수 log, while문에서 n의 범위를 줄여줌 n이 소수가 아니라면, n은 루트n 이하의 소인수를 갖는다. i==2부터 차례대로 n을 나눌 수 있다면 i로 n을 더이상 나눌 수 없을 때까지 나누면서 진행한다. 과정이 끝나면 n=1 또는 n=소수가 된다. ll n; cin >> n; vector p; for (ll i = 2; i * i 2020. 1. 30.
후속 노드 그래프 (Successor graph), 희소테이블 모든 정점에 대해 인접한 정점이 단 하나인 그래프로, 함수형 그래프(functional graph)라고도 부른다. succ(x)의 형태로 후속 노드 그래프의 모든 간선을 표현할 수 있기 때문. 후속 노드 그래프는 하나 이상의 컴포넌트로 구성돼 있고, 각각의 컴포넌트는 사이클 '하나'와 그 사이클로 가는 경로로 구성되어 있다. (그래프의 끝에 사이클이 단 하나 달린 형태) 트리구조와 유사하다.(트리에서 루트노드가 자식중 어딘가 가리키고 있다면 후속노드 그래프가 된다. -- 그건 더이상 트리가 아님) 희소테이블 p[u][k]에 이 구조를 담아 푸는 문제가 대부분 - 정점 u에서 k번 이동한 후의 정점을 log시간에 구하기 기본문제 : https://cses.fi/problemset/task/1750 널리쓰이.. 2020. 1. 29.
사이클 검출 ㅁ 양방향 그래프 https://cses.fi/problemset/task/1669 prv배열과 사이클의 끝점, 시작점을 잘 캐치하면 된다. 양방향 그래프가 주어질 때 사이클이 없으면 IMPOSSIBLE출력, 있으면 아무 사이클이나 사이클을 이루는 정점의 크기와 정점번호들 순서대로 출력 const int MAX = 1e5 + 2; int n, m, prv[MAX], st, en; vector adj[MAX]; bool vst[MAX], fin[MAX]; void dfs(int curr, int pr=0) { vst[curr] = true; for (int next : adj[curr]) { if (!vst[next]) { prv[next] = curr; dfs(next,curr); } //다음 정점이 방.. 2020. 1. 23.
이분그래프 (bipartite graph) 어떤 그래프의 모든 노드를 두가지 색 중 하나로 칠하되, 이웃 노드의 색이 모두 다르게 만들 수 있다면 그 그래프는 이분그래프이다. 홀수개의 간선으로 이뤄진 사이클이 없으면 이분그래프이다! void dfs(int u, int p) { vst[u] = vst[p]==1?2:1; for (int v : adj[u]) { if (v == p) continue; if (vst[v] && !fin[v] && vst[v]==vst[u]) isNotBipartite = true; else if (!vst[v]) dfs(v, u); } fin[u] = true; } 2020. 1. 22.

티스토리툴바