본문 바로가기

Algorithm

 (13)
알고리즘 미니 노트 대회 중 코딩 시간과 실수를 줄이기 위해 자주 쓰이는 알고리즘을 기존의 템플릿을 베이스로 템플릿화한다. 시시때때로 바뀌는 코딩 스타일에 맞춰 템플릿도 변화할 예정. 순서는 내 체감 난이도순이다. 오류, 오타 지적 감사합니다. 1. 분할 정복을 이용한 거듭제곱 exponentiation by squaring, fast power ll _pow(ll x, ll y) { ll ret = 1; for(; y; x = x * x % mod, y >>= 1) if(y & 1) ret = ret * x % mod; return ret; } 2. 선형 시간 조합 계산 calculate combination in O(n) time, nCr const int X = N 0) { ch.push_back(p2); break;..
선택 정렬의 개선 데추주를 위해 선택 정렬을 짜는데 무언가 익숙함이 느껴졌다. 어 이거... 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..
경로 가중치 합 hld 구현 코드 특징 : 맞는지 모름 앳코더에서 Proof by AC 성공 #include using namespace std; #define fastio cin.tie(0)->sync_with_stdio(0) #define X first #define Y second typedef pair pii; const int N=1e5+1; struct Segment { int a[N]; int tree[4*N],lazy[4*N]; void init(int l,int r,int i) { if(l==r) { tree[i]=a[l]; return; } int m=l+r>>1; init(l,m,i
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; ..

티스토리툴바