본문 바로가기

Algorithm

알고리즘 모음 ( 개인 노트용 )

깃허브에 올리고 싶었지만 깃허브는 너무 어렵다. (상시 수정합니다.) (재정리가 필요해보인다.)

 

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

'Algorithm' 카테고리의 다른 글

선택 정렬의 개선  (0) 2021.11.19
알고리즘 모음 ( 개인 노트용 )  (3) 2021.01.24
  • 비키라 2021.03.30 15:10 신고

    O(n) 전처리 + O(log n) 소인수분해 알고리즘에 대해 찾아보는거 추천합니다!
    에라토스테네스 체랑 매우 유사해요

    • HeeJaYaa 2021.03.30 16:28 신고

      O(N) 에라토스테네스의 체를 응용하는 것인가요? 왠지 코포에서 본 느낌이네요..
      최근에 폴라드-로를 배워서 소인수분해는 뇌 비우고 이거 쓰는 중입니다 ㅎㅎ

    • 비키라 2021.03.30 22:07 신고

      어 생각해보니 O(N lg lg N)이네요. 보통 spf(smallest prime factor)
      https://www.geeksforgeeks.org/prime-factorization-using-sieve-olog-n-multiple-queries/

      헐 폴라드 로.... ㄷ