깃허브에 올리고 싶었지만 깃허브는 너무 어렵다. (상시 수정합니다.) (재정리가 필요해보인다.)
1. Segment Tree
구현체는 간단하나 응용이 어렵다는 생각이 듦. 구현 복잡하고 응용 다양한 코드는 제출코드 참고.
2042번: 구간 합 구하기
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄
www.acmicpc.net
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll arr[1<<21],sz=1;
void update(int i,ll val)
{
for(arr[i+=sz]=val;i>1;i>>=1) arr[i>>1]=arr[i]+arr[i^1];
}
ll sum(int l,int r)
{
ll res=0;
for(l+=sz,r+=sz+1;l<r;l>>=1,r>>=1){
if(l&1) res+=arr[l++];
if(r&1) res+=arr[--r];
}
return res;
}
int main()
{
int n,m,k;
scanf("%d%d%d",&n,&m,&k);
int q=m+k;
sz=1<<(int)ceil(log2(n));
for(int i=0;i<n;i++) scanf("%lld",&arr[sz+i]);
for(int i=sz-1;i>=1;i--) arr[i]=arr[i<<1]+arr[i<<1|1];
while(q--){
ll a,b,c;
scanf("%lld%lld%lld",&a,&b,&c);
if(a==1) update(b-1,c);
else printf("%lld\n",sum(b-1,c-1));
}
}
2. Sieve of Eratosthenes
bool np[1000001];
np[0]=np[1]=true;
for(ll i=2;i<=n;i++) if(!np[i]) for(ll j=i*i;j<=n;j+=i) np[j]=true;
3. factorial inverse O(N+logP) for nCr
#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int fac[1000001],inv[1000001];
int fpow(int x,int y)
{
int res=1;
while(y){
if(y&1) res=1LL*res*x%mod;
x=1LL*x*x%mod;
y>>=1;
}
return res;
}
int C(int n,int r)
{
return 1LL*fac[n]*inv[r]%mod*inv[n-r]%mod;
}
int main()
{
int n,r;
scanf("%d%d",&n,&r);
fac[0]=inv[0]=1;
for(int i=1;i<=n;i++) fac[i]=1LL*fac[i-1]*i%mod;
inv[n]=fpow(fac[n],mod-2);
for(int i=n-1;i>0;i--) inv[i]=1LL*inv[i+1]*(i+1)%mod;
printf("%d",C(n,r));
}
4. mobius_inversion
int mu[50001];
void make_mu()
{
mu[1]=1;
for(int i=1;i<=50000;i++)
for(int j=2*i;j<=50000;j+=i) mu[j]-=mu[i];
}
x의 약수 중 제곱수 존재: mu[x]=0
x의 소인수 (2*k)개: mu[x]=1
x의 소인수 (2*k+1)개: mu[x]=-1
5. LIS O(NlogN)
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,ans=0;
vector<int> v;
v.push_back(0);
scanf("%d",&n);
while(n--){
int x;
scanf("%d",&x);
if(x>v.back()){
v.push_back(x);
ans++;
}
else v[lower_bound(v.begin(),v.end(),x)-v.begin()]=x;
}
printf("%d",ans);
}
6. 기하 테크닉
11563번: 연돌이와 고잠녀
첫 줄에는 신촌에 연결된 도로의 개수 n과 안암에 연결된 도로의 개수 m(1 ≤ n, m ≤ 2,000)이 주어진다. 이어지는 n줄에 걸쳐 xs, ys, xe, ye가 주어진다. (-10,000 ≤ xs, ys, xe, ye ≤ 10,000) 이는 신촌에 연
www.acmicpc.net
17386번: 선분 교차 1
첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. 세 점이 일직선 위에 있는 경우는 없다.
www.acmicpc.net
7. 다익스트라
1753번: 최단경로
첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다.
www.acmicpc.net
#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
typedef pair<int,int> pii;
const int INF=987654321;
int main()
{
int v,e,st;
vector<pii> ad[20005];
scanf("%d%d%d",&v,&e,&st);
for(int i=0;i<e;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
ad[a].push_back({c,b});
}
vector<int> d(v+1);
fill(d.begin(),d.end(),INF);
priority_queue<pii,vector<pii>,greater<pii>> pq;
pq.push({0,st});
d[st]=0;
while(!pq.empty()){
int dist=pq.top().X;
int idx=pq.top().Y;
pq.pop();
if(d[idx]!=dist) continue;
for(int i=0;i<ad[idx].size();i++){
int cost=ad[idx][i].X;
int nidx=ad[idx][i].Y;
if(d[nidx]>dist+cost){
d[nidx]=dist+cost;
pq.push({d[nidx],nidx});
}
}
}
for(int i=1;i<=v;i++){
if(d[i]==INF) puts("INF");
else printf("%d\n",d[i]);
}
}
8. GCD
ll gcd(ll a,ll b)
{
for(;b;a%=b,swap(a,b));
return a;
}
9. Convex Hull
#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
typedef pair<int,int> pii;
typedef long long ll;
vector<pii> d;
int ccw(pii a,pii b,pii c)
{
ll res=1LL*(b.X-a.X)*(c.Y-a.Y)-1LL*(b.Y-a.Y)*(c.X-a.X);
return res>0?1:res<0?-1:0;
}
bool cmp(pii a,pii b)
{
int res=ccw(d[0],a,b);
return res?res>0:a<b;
}
int main()
{
int n;
scanf("%d",&n);
d.resize(n);
for(int i=0;i<n;i++){
scanf("%d%d",&d[i].X,&d[i].Y);
if(d[0]>d[i]) swap(d[0],d[i]);
}
sort(d.begin()+1,d.end(),cmp);
vector<pii> ch; // maybe stack
ch.push_back(d[0]),ch.push_back(d[1]);
int nd=2; // next_d
while(nd<n){
while(ch.size()>=2){
pii d2=ch.back();
ch.pop_back();
pii d1=ch.back();
if(ccw(d1,d2,d[nd])>0){
ch.push_back(d2);
break;
}
}
ch.push_back(d[nd++]);
}
printf("%d",ch.size());
}
10. 인접행렬 거듭제곱
12916번: K-Path
첫 번째 줄에 N, K ( 1 ≤ N ≤ 100, 1 ≤ K ≤ 109) 이 공백을 구분으로 주어진다. 다음 N개의 줄에 걸쳐 민호가 작성한 인접 행렬이 주어진다. i번 줄의 j번 수가 1이면 i번 마을과 j번 마을의 길이 있
www.acmicpc.net
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
typedef long long ll;
const ll mod=1e9+7;
int n,k;
ll ANS[100][100];
ll A[100][100];
void mult()
{
ll T[100][100]={};
rep(i,n) rep(j,n) rep(k,n) T[i][j]=(T[i][j]+ANS[i][k]*A[k][j])%mod;
rep(i,n) rep(j,n) ANS[i][j]=T[i][j];
}
void matpow()
{
ll T[100][100]={};
int i,j,k;
rep(i,n) rep(j,n) rep(k,n) T[i][j]=(T[i][j]+A[i][k]*A[k][j])%mod;
rep(i,n) rep(j,n) A[i][j]=T[i][j];
}
int main()
{
scanf("%d%d",&n,&k);
rep(i,n) ANS[i][i]=1;
rep(i,n) rep(j,n) scanf("%lld",&A[i][j]);
while(k){
if(k&1) mult();
matpow();
k>>=1;
}
ll ans=0;
rep(i,n) rep(j,n) ans=(ans+ANS[i][j])%mod;
printf("%lld",ans);
}
11. 루카스 정리 (1도 쓸모 없다)
11402번: 이항 계수 4
첫째 줄에 \(N\), \(K\)와 \(M\)이 주어진다. (1 ≤ \(N\) ≤ 1018, 0 ≤ \(K\) ≤ \(N\), 2 ≤ \(M\) ≤ 2,000, M은 소수)
www.acmicpc.net
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int fac[2000],inv[2000]; // mod_max
int mod;
int fpow(int x,int y)
{
int res=1;
while(y){
if(y&1) res=1LL*res*x%mod;
x=1LL*x*x%mod;
y>>=1;
}
return res;
}
int lucas(ll n,ll k)
{
int res=1;
while(k){
int n1=n%mod,k1=k%mod;
if(n1<k1) return 0;
res=1LL*res*fac[n1]%mod*inv[k1]%mod*inv[n1-k1]%mod;
n/=mod,k/=mod;
}
return res;
}
int main()
{
ll n,k;
scanf("%lld%lld%d",&n,&k,&mod);
fac[0]=inv[0]=1;
for(int i=1;i<mod;i++) fac[i]=fac[i-1]*i%mod;
inv[mod-1]=fpow(fac[mod-1],mod-2);
for(int i=mod-2;i>0;i--) inv[i]=inv[i+1]*(i+1)%mod;
printf("%d",lucas(n,k));
}
12. Sparse Table
17435번: 합성함수와 쿼리
함수 f : {1, 2, ..., m}→{1, 2, ..., m}이 있다. 이때 fn : {1, 2, ..., m}→{1, 2, ..., m}을 다음과 같이 정의하자. f1(x) = f(x) fn+1(x) = f(fn(x)) 예를 들어 f4(1) = f(f(f(f(1))))이다. n과 x가 주어질 때 fn(x)를 계산하는
www.acmicpc.net
#include<bits/stdc++.h>
using namespace std;
int f[200001][19];
int main()
{
int m,q;
scanf("%d",&m);
for(int i=1;i<=m;i++) scanf("%d",&f[i][0]);
for(int j=1;j<19;j++) for(int i=1;i<=m;i++) f[i][j]=f[f[i][j-1]][j-1];
scanf("%d",&q);
while(q--){
int n,x;
scanf("%d%d",&n,&x);
for(int i=0;i<19;i++) if(n&(1<<i)) x=f[x][i];
printf("%d\n",x);
}
}
13. LCA
11438번: LCA 2
첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정
www.acmicpc.net
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+1;
vector<int> ad[N];
int dep[N],par[N][17];
void make_tree(int cur,int prv) {
for(auto nxt : ad[cur]){
if(nxt==prv) continue;
dep[nxt]=dep[cur]+1, par[nxt][0]=cur;
make_tree(nxt,cur);
}
}
int lca(int u,int v) {
if(dep[u]<dep[v]) swap(u,v);
int diff=dep[u]-dep[v];
for(int i=0;i<17;i++) if(diff&(1<<i)) u=par[u][i];
if(u==v) return u;
for(int i=16;i>=0;i--)
if(par[u][i]!=par[v][i]) u=par[u][i], v=par[v][i];
return par[u][0];
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n; cin >> n;
for(int i=1;i<n;i++){
int u,v; cin >> u >> v;
ad[u].push_back(v);
ad[v].push_back(u);
}
make_tree(1,0);
for(int j=1;j<17;j++) for(int i=1;i<=n;i++)
par[i][j]=par[par[i][j-1]][j-1];
int q; cin >> q;
while(q--){
int u,v; cin >> u >> v;
cout << lca(u,v) << '\n';
}
}
14. 위상 정렬
2252번: 줄 세우기
첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이
www.acmicpc.net
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,m;
scanf("%d%d",&n,&m);
vector<int> id(n+1);
vector<int> ad[32001];
while(m--){
int a,b;
scanf("%d%d",&a,&b);
id[b]++;
ad[a].push_back(b);
}
queue<int> q;
for(int i=1;i<=n;i++) if(!id[i]) q.push(i);
for(int i=0;i<n;i++){
if(q.empty()){
printf("-1");
return 0;
}
int idx=q.front();
printf("%d ",idx);
q.pop();
for(int nidx: ad[idx])
if(--id[nidx]==0) q.push(nidx);
}
}
15. 벨만-포드, SPFA, 플로이드 와샬 (추가 예정) (귀찮음)
16. 최소 스패닝 트리 (크루스칼 알고리즘)
1197번: 최소 스패닝 트리
첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이
www.acmicpc.net
#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
typedef pair<int,pair<int,int>> piii;
vector<int> p;
int fnd(int x)
{
if(p[x]==x) return x;
return p[x]=fnd(p[x]);
}
bool uni(int a,int b)
{
a=fnd(a),b=fnd(b);
if(a==b) return false;
p[max(a,b)]=min(a,b);
return true;
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
p.resize(n+1);
for(int i=1;i<=n;i++) p[i]=i;
vector<piii> e(m);
for(int i=0;i<m;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
e[i].X=c, e[i].Y={a,b};
}
sort(e.begin(),e.end());
int ans=0,cnt=0;
for(int i=0;;i++){
if(uni(e[i].Y.X,e[i].Y.Y)){
ans+=e[i].X;
if(++cnt==n-1) break;
}
}
printf("%d",ans);
}
17. 행렬 거듭제곱 DP 일반화
14440번: 정수 수열
첫째 줄에 x, y, a0, a1, n이 주어진다. (1 ≤ x, y ≤ 99, 0 ≤ n < 108) a0과 a1은 A0, A1의 마지막 두 자리이다.
www.acmicpc.net
