본문 바로가기

알고리즘225

소인수 분해, 약수의 개수, 오일러 피함수 에라토스테네스 :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.
CSES PS - investigation (다익스트라, 위상정렬) https://cses.fi/problemset/task/1202 볼륨이 크다. 사이클이 허용된 가중치가 있는 방향그래프가 주어진다. 시작점 1에서 끝점 n까지 최소 비용으로 이동할 때, (1)그 비용 (2) 가능한 경로의 수, (3) 가능한 경로 중 가장 적은 간선을 지나치는 경우 그 간선의 수, (4) 가장 많은 간선을 지나는 경우 그 간선의 수. (1),(2),(3),(4)를 모두 구하는 문제 (1)은 다익스트라로 풀 수 있고, (2),(3),(4)는 DAG일 때 dp로 풀 수 있는 내용이다. 사이클이 있는 그래프라고 해도 최소비용으로 이동하는 경로는 항상 DAG임이 분명하다. 1. 주어진 그래프에서 유효한 즉, 최소비용 경로에 해당하는 간선들만 남겨서 DAG를 만든다. dist(1~u) + w +.. 2020. 1. 29.
codeforces 563 div2 D - Ehab and the Expected XOR Problem (XOR, prefix xor) https://codeforces.com/contest/1174/problem/D xor문제는 기발한게 많은 것 같다. subsegment란, 맨 앞 혹은 맨 뒤 요소를 포함한 subarray이다. n과 x를 입력받아서 숫자 배열을 하나 만든다 ( ai < (1 2020. 1. 29.

티스토리툴바