본문 바로가기

Algorithm

(11)
선택 정렬의 개선 데추주를 위해 선택 정렬을 짜는데 무언가 익숙함이 느껴졌다. 어 이거... RMQ? RMQ는 세그먼트 트리를 이용하면 각 쿼리를 $O(logN)$에 구할 수 있음이 잘 알려져 있고, 선택 정렬을 시행할 때 필요한 쿼리의 수는 $N$번이다. 세그먼트 트리를 전처리하는 데에도 $O(NlogN)$이 필요하므로, 최종 시간복잡도 $O(NlogN)$에 배열을 정렬할 수 있다. BOJ 2751에 제출해보니 메모리와 시간 면에서 그다지 효율적이지는 않아도 나름 선전하는 모습을 보여줬다. #include using namespace std; #define nm (nl+nr>>1) typedef pair pii; const int N = 1e6+1; int n,a[N]; pii tree[4*N]; void init(in..
Centroid Decomposition 트리에서 센트로이드를 잡고 분할 정복을 돌리는 테크닉. 5820번: 경주 첫째 줄에 N과 K가 주어진다. 둘째 줄부터 N-1개 줄에는 H[i][0], H[i][1], L[i]가 주어진다. (1 ≤ N ≤ 200,000, 1 ≤ K ≤ 1,000,000) www.acmicpc.net #include using namespace std; typedef pair pii; const int N=2e5+1; const int K=1e6+1; const int INF=1e9; int n,k; int sz[N],use[N],chk[K]; vector ad[N]; vector tree; int get_size(int cur,int prv) { sz[cur]=1; for(auto [nxt,w] : ad[cur]){ if..
Miller–Rabin primality test && Pollard's rho algorithm [BOJ 4149]의 코드로 설명을 대신하겠다. 왜 클래스의 이름을 거창하게 'number theory' 라고 지었는지는 비밀이다. :) #include using namespace std; #define fastio ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) typedef long long ll; typedef __int128 i128; typedef vector vec; struct int_nt { ll mul(ll x,ll y,ll mod) { return (i128)x*y%mod; } ll gcd(ll x,ll y) { for(;y;x%=y,swap(x,y)); return x; } ll lcm(ll x,ll y) { return x/gcd(x,y)*y; ..
Segment Tree and Lazy Propagation 드디어 느리게 갱신하는 세그먼트 트리의 구현을 끝냈다. update에서 r을 e로 쓴 오타를 몇 시간동안 찾지 못해 고생했다. + : 연습문제들을 풀어보니 f, ff 함수를 만드는 것보단 직접 쓰는 것이 편한 것 같다. 문제를 더 풀고 나서 판단하자. ++ : f, ff 함수를 없앴다. lazy의 형태가 다양해서 템플릿처럼 만든 코드도 보기 힘들다. +++ : tree와 lazy를 벡터에서 배열로 바꾸고 크기를 2의 거듭제곱수로 바꿔주는 부분을 없앴다. 10999번: 구간 합 구하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고..
연속합 최대 Segment Tree 말 그대로 구간에서 최대 연속합을 구해주는 세그먼트 트리이다. 금광 세그로 유명하고, 금광 문제를 풀기 위해 배웠다. 아이디어가 신기함! 진한님의 코드를 적극 참고했습니다. 16993번: 연속합과 쿼리 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j : Ai, Ai+1, ..., Aj에서 가장 큰 연속합을 출력한다. (1 ≤ i ≤ j ≤ N) 수열의 인덱스는 1부터 시작 www.acmicpc.net #include using namespace std; #define fastio ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) typedef long long ll; const ll INF=1e18; ..