pseong

중국인의 나머지 정리가 무엇을 의미하는지는 나무위키에 잘 설명이 되어있다. 중국인의 나머지 정리 - 나무위키 (namu.wiki) 보통 중국인의 나머지 정리라 하면 모든 m이 서로소여야 한다. 하지만 서로소가 아닐때도 해를 구하고 싶을때가 있을 것이다. 이런 경우에는 두 개의 합동식을 하나로 합친다. 계속 이렇게 합쳐 주다가 마지막 한 개의 합동식만 남았을 때 답을 구해주면 해결된다. 따라서 두 개의 합동식을 합치는 방법만 알면 문제를 풀 수 있다. x ≡ a1 ( mod x1 ) x ≡ a2 ( mod x2 ) 먼저 이렇게 두 개의 합동식이 있다고 하자. g = gcd(x1, x2) 라고 하자. 아래 두 개의 식이 성립하므로 x ≡ a1 (mod g) x ≡ a2 (mod g) 다음 식이 성립한다고 할..

제 1종 스털링 수 모든 노드의 outdegree가 1이고 indegree도 1인 노드가 n개인 그래프에서 k개의 사이클이 생기는 경우의 수를 의미한다. 이 그래프는 일대일 대응이므로 간선은 전단사 함수라고 할 수 있다. s(n,k) = s(n−1, k−1) + (n−1)s(n−1, k) 어떤 한 노드를 self loop라고 했을 때 n-1개에서 k-1개의 사이클이 생기는 경우의 수는 s(n-1, k-1) 이다. 어떤 한 노드를 제외하고 n-1개에서 k개의 사이클이 생기는 경우의 수는 s(n-1, k) 이고 어떤 한 노드를 이제 이미 만들어진 k개의 사이클로 넣어야 한다. 이 경우 어떤 한 노드의 친구를 정해고 그 친구와 함께 사이클에 들어간다고 하면 친구를 만드는 경우의 수는 n-1개이고 따라서 (n-..

사실 어려운 알고리즘 중에서 세그먼트 트리만 제대로 쓸 줄 안 다면 정말 정말 편하다. 세그 문제가 아닌데도 세그로 풀리는 문제가 많기 때문이다. 세그먼트 트리만 깊게 파서 나쁠건 없다고 생각한다. 공부 대비 가성비가 정말 좋은 알고리즘 이다. 세그먼트 트리의 구조 세그먼트 트리는 간단하게 부모의 노드가 자손의 노드들 중 리프 노드를 관리한다고 생각하면 된다. 만약 입력값이 1부터 6까지 주어졌다고 생각해보자. 세그먼트 트리의 모양은 아래와 같다. 노드1 : 인덱스 1부터 6까지 관리하는 노드 노드2 : 인덱스 1부터 3까지 관리하는 노드 노드3 : 인덱스 4부터 6까지 관리하는 노드 노드4 : 인덱스 1부터 2까지 관리하는 노드 노드5 : 인덱스 3부터 3까지 관리하는 노드 이렇게 구간을 절반씩 나눠서..