Centroid of Tree centroid란 트리에서 어떤 노드(와 연결된 엣지들)를 삭제했을 때, 분리된 component의 크기가 n/2 이하가 되는 노드를 말한다. centroid는 트리에서 반드시 최소 하나는 존재하며, 최대 2개를 가질 수도 있다. centroid를 찾는 방법은 두 번의 dfs를 돌려보면 된다. 첫 번째 dfs(subtreeDFS) 에서는 어떤 임의의 노드 x를 트리의 루트라고 가정하고 dfs를 시작한다. x 노드의 subtree가 갖고 있는 노드의 개수를 subtree[] 배열에다가 저장해놓는다. 두 번째 dfs(findCentroid) 에서는 구해놓은 subtree[]값을 통해 현재 노드 i를 삭제했을 경우, 그로 인해 분할되는 component들(subtree)의 값이 ..
위계가 존재하는 트리에서 두 노드 a와 b가 있을 때, a가 b의 ancestor(조상)인지 확인해야 할 때 사용하는 방법이다. 트리의 루트노드에서부터 dfs순회를 시작해서 preorder로 한 번, postorder로 한 번 각각 돌아준다. 그러면 각 순회 별로 노드의 방문 순서를 기록을 해둘텐데, 당연히 preorder의 순서와 postorder의 순서는 다를 것이다. 여기서 생기는 특징은 preorder는 루트노드에서 가까울수록 순회 순서가 빠를 것이고, postorder는 루트노드에서 가까울수록 순회 순서가 느리다. 이를 이용해서 ancestor를 판별할 수 있다. 바로 a가 b의 ancestor라면 preorder로 돌았을 때는 a가 b보다 먼저 등장할 것이고, postorder로 돌았을 때는 ..
포함배제의 원리는 여러개의 집합이 있고, 각 집합간의 교집합에 속하는 원소의 개수를 알 때, 총 합집합의 원소의 개수를 구하는 방법이다. 집합이 두개나 세개일 때 구하는 방법은 중학교 수학시간에 배웠다. 집합이 두개(A,B) 일 때는 |A합B| = |A|+|B|-|A교B|이고, 세개(A,B,C)일 때는 |A합B합C| = |A|+|B|+|C|-|A교B|-|B교C|-|A교C|+|A교B교C| 로 구할 수 있다. 그렇다면 집합의 개수가 이보다 더 많아질 때는 어떻게 계산할까? 집합의 개수가 n개일 때 합집합을 구하는 공식은 3개일 때의 공식에서 보면 살짝 유추할 수 있는데, 바로 집합의 교집합이 홀수개일 때는 더하고, 짝수개일 때는 빼는 것이다. A,B,C와 A교B교C교는 홀수개였으므로 더했고 A교B, B교C,..
확장 유클리드 정리는 $ax+by=c$ ($a,b,c$는 상수 $ x,y$는 정수인 미지수)를 만족시키는 $x,y$를 찾는 알고리즘이다. 예를 들어서 $a=3,b=4,c=10$이라면 $x=2,y=1$을 찾을 수 있게 해주는 것이다. 여기서 반드시 충족되야할 조건은, $a$와 $b$의 최대공약수가 $c$의 약수여야 한다는 것이다. 수식으로 표현하자면 $gcd(a,b)=d$일 때, $d | c$를 만족해야 한다는 것이다. 위 식에선 d=1이고 c=10이므로 충족한다. 이를 충족시키지 못하면 $x,y$는 존재하지 않는다. 그러면 본격적으로 $ax+by=c$를 만족하는 $x,y$는 어떻게 구할까? 바로 기존의 유클리드 알고리즘을 거꾸로 거슬러 올라가기만 하면 된다. 유클리드 알고리즘은 $gcd(a,b)=gcd(..
소인수분해가 필요한 문제는 크게 두 가지 방법으로 풀 수 있다. 1. 소인수분해를 시행하는 횟수가 시간에 큰 영향을 주지 않을 때 i를 2부터 루트n 까지 돌면서 n의 소인수에 해당한다면 추가하고 n을 i로 나눠주면 된다. 다 끝난 뒤에 n값이 1이 아닌지만 체크해주면 된다. 1234567891011121314151617181920#include #include#include typedef long long ll;using namespace std;map mp;int main(){ ll n; scanf("%lld", &n); for(ll i=2 ; i*i1) mp[n]++; for(auto &here:mp) printf("%lld %lld\n",here.first,here.second); return 0..