알고리즘/메모44 난수, 랜덤 #include using namespace std; int main(){ random_device rd; //진짜 난수 발생 mt19937 mt(rd()); uniform_int_distribution rnd(0, n-1); //min-max 폐구간 범위 //rnd(mt) -> 0~n-1사이 난수 생성 } random_device 객체 rd는 rd()로 unsigned int범위(0~4294967295) 난수를 생성한다. mt19337은 균등한 분포의 난수를 만들어주는 난수 엔진이다. 이 객체를 만들 때 생성자에 random_divce 객체를 넣어서 만들면 된다. uniform_int_distribution도 유사한 난수 엔진인 것으로 보인다. 2020. 8. 28. 머지소트 트리 1. update가 이뤄지지 않으며 구간 [s,e]에서 x이상 원소의 수를 물어보는 쿼리 2. 포인트 update가 이뤄질 수 있으며 구간 [s,e]에서 x이상 원소의 존재성과 그 최소값을 물어보는 쿼리 위 1,2번 경우 기존 세그트리를 약간만 변형하여 머지소트 트리를 만들어 풀 수 있다. 1번은 각 세그 노드마다 벡터를, 2번은 set을 쓴다면 이분탐색으로 쉽게 풀 수 있다. 3. 포인트 update가 이뤄질 수 있으며 구간 [s,e]에서 x이상 원소의 수를 물어보는 쿼리 3번 경우, 세그트리에 splay tree나 treap이나 데카르트트리따위를 넣어 해결할 수 있다고 한다. ->구현 매우 어려움. gcc 내장 트리를 사용한다면 쉬워질 수 있을 것 같다. https://www.acmicpc.net/p.. 2020. 6. 2. 확장 유클리드 공부한 블로그 : https://viruz.tistory.com/entry/EEA Extended Euclidean algorithm 확장 유클리드 알고리즘(Extended Euclidean algorithm)은 이름에서 알 수 있듯 유클리드 알고리즘의 확장 버전이다. 기존 유클리드 알고리즘이 두 정수 $a$, $b$의 $GCD$만 구했다면, 확장 유클리드 알고리즘은.. viruz.tistory.com 다음과 같은 식을 선형 방정식이라고 한다. ax + by = c 여기서 정수해 x,y는 c가 gcd(a,b)로 나눠지는 경우 존재한다. gcd(a,b) = g라고 하고 ax + by = g의 값을 구하는 과정은 https://www.youtube.com/watch?v=PmwLXveLtqc참고. 유튜브 속 .. 2020. 5. 5. 1차원 직선 위 겹치는 선분들 모든 '교차'하는 선분 쌍에 대한 질의 https://acm-iupc.tistory.com/entry/%EC%84%A0%EB%B6%84%EC%97%90-%EB%8C%80%ED%95%9C-%EC%A7%88%EC%9D%98 *교차하는 모든 선분 쌍의 수 nlogn에 구하는 법은 못 찾겠고 생각이 안난다 (20.4.5) 겹치는 선분에 대한 생각 정리용 포스트 https://www.acmicpc.net/problem/11000 위 문제에서 어떤 시간에 필요한 강의실의 수 = 그 시점에 겹치는 선분의 수 total = 겹치는 선분 쌍의 수 mx = 최대로 겹칠 때 겹치는 선분 수 const int MAX = 2e5 + 4; int n, ps[MAX],mx, total; P line[MAX]; int main() .. 2020. 4. 5. 이전 1 2 3 4 5 ··· 11 다음
