각종 알고리즘

Disjoint Set

#include<stdio.h>
#define SIZE 110
class Disjoint_Set{
	private:
		int root[SIZE],rank[SIZE],cnt[SIZE]; 
	public:
		void Make_Set(int x){
			root[x]=x;
			rank[x]=0;
			cnt[x]=1;
		}
		int Find_Set(int x){
			if(x==root[x]) return x;
			return Find_Set(root[x]);
		}
		//Union by Rank
		void Union(int a,int b){
			a=Find_Set(a); b=Find_Set(b);
			if(a==b) return;
			int t=cnt[a]+cnt[b];
			if(rank[a]>rank[b]){
				root[b]=a,cnt[a]+=cnt[b];
			}
			else{
				root[a]=b,cnt[b]+=cnt[a];
				if(rank[a]==rank[b])
					rank[b]++;
			}
		}
		int Cnt(int x){
			return cnt[Find_Set(x)];
		}
};
int IMPORTANT = 1;
int main(){
	Disjoint_Set DS;
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) DS.Make_Set(i);
	while(m--){
		int a,b;
		scanf("%d%d",&a,&b);
		DS.Union(a,b);
	}
	int ans = DS.Cnt(IMPORTANT) - 1; //자기 자신은 제외 
	printf("%d",ans);
} 

 

Graph

최소 비용 신장 트리 

[크루스칼]

//pentagon@sasa.hs.kr 
#include<bits/stdc++.h>
#define ll long long
const int INF = 1e9;
using namespace std;
int n,m,ans,root[10010];
vector<tuple<int,int,int>> E;
int find(int x){
	if(x==root[x]) return x;
	return root[x]=find(root[x]);
}
void Union(int x,int y){
	x=find(x); y=find(y);
	if(x==y) return;
	root[x]=y;
}
int main(){
	ios::sync_with_stdio(false); cin.tie(0);
	cin>>n>>m;
	while(m--){
		int x,y,w; 
		cin>>x>>y>>w;
		E.push_back(make_tuple(w,x,y));
	}
	for(int i=1;i<=n;i++) root[i]=i;
	sort(E.begin(),E.end());
	int cnt=0,id=0;
	for(auto &k:E){
		int x,y,w;
		tie(w,x,y)=k;
		x=find(x); y=find(y);
		if(x==y) continue;
		else{
			if(w%2) ans+=w;
			Union(x,y);
			cnt++;
		}
		if(cnt==n-1) break;
	}
	cout<<ans;
}

[프림]

아래 링크 보고 공부하는 거 추천 

https://www.weeklyps.com/entry/%ED%94%84%EB%A6%BC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Prims-algorithm

#include<stdio.h>
#define N 11
#define INF 2e9
#define min(a,b) ((a)<(b)?(a):(b))
int arr[N],n,k,sum,dis[N],cnt;
bool visit[N]; 
void prim(int s){
	while(cnt<n-1){
		visit[s]=1;
		int min_i,min_w=INF;
		for(int i=1;i<=n;i++) dis[i]=min(dis[i],arr[s]+arr[i]);
		for(int i=1;i<=n;i++)
			if(!visit[i]&&(dis[i]<min_w))
				min_i=i,min_w=dis[i];
		sum+=dis[min_i]; cnt++; s=min_i;
	}
}
int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++) scanf("%d",arr+i);
	for(int i=1;i<=n;i++) dis[i]=INF;
	dis[1]=0; prim(1);
	if(k>=sum) printf("Assemble");
	else printf("%d",sum-k);
}

 

위상정렬

#include<stdio.h>
int n,m,cnt,print[201];
bool adj[201][201],visit[201];
int return_start(){
	for(int i=1;i<=n;i++){
		if(visit[i]) continue;
		bool flg=1;
		for(int j=1;j<=n;j++)
			if(adj[j][i]){
				flg=0;
				break;
			}
		if(flg) return i;
	}
	return -1;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=0,a,b;i<m;i++){
		scanf("%d%d",&a,&b);
		adj[a][b]=1;
	}
	bool flag=0;
	while(cnt<n){
		int s=return_start();
		if(s==-1) break;
		visit[s]=1;
		print[cnt++]=s;
		for(int i=1;i<=n;i++) adj[s][i]=0;
	}
	if(cnt<n) printf("-1");
	else{
		for(int i=0;i<n;i++)
			printf("%d\n",print[i]);
	}
}

 

플로이드 워셜

#include<stdio.h>
#define INF 1<<20
int n,m,arr[20][20];
void input(){
	for(int i=1;i<=10;i++)for(int j=1;j<=10;j++)
		arr[i][j]=INF;
	scanf("%d%d",&n,&m);
	for(int i=0,a,b,w;i<m;i++){
		scanf("%d%d%d",&a,&b,&w);
		arr[a][b]=arr[b][a]=w;
	}
}
void Floyd(){
	for(int m=1;m<=n;m++)
		for(int s=1;s<=n;s++)
			for(int e=1;e<=n;e++)
				if(arr[s][e]>arr[s][m]+arr[m][e])
						arr[s][e]=arr[s][m]+arr[m][e];
}
int main(){
	input();
	Floyd();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			printf("%d¿¡¼­ %d·Î °¡´Â ÃִܰŸ®:%d\n",i,j,arr[i][j]);
	return 0;
}

 

KMP

//KMP Algorithm 구현

#include<stdio.h>
#define N 10010
int n,m,pi[N];
//p -> pattern 
void preprocess(char*p){
	int j=1,k=0;
	pi[1]=0;
	while(j<=m){
		if(k==0 || p[j]==p[k]){
			j++; k++; pi[j]=k;
		}
		else
			k=pi[k];
	}
} 
void Knuth_Morris_Pratt(char*str,char*p){
	preprocess(p);
	int i=1,j=1;
	while(i<=n){
		if(j==0 || str[i]==p[j])
			i++,j++;
		else 
			j=pi[j];
		if(j==m+1){
			printf("%d번째 문자에서 패턴이 발생!\n",i-m);
			j=pi[j];
		}
	}
}
int main(){
	//n,m -> 원문자열, 패턴문자열의 길이
	scanf("%d%d",&n,&m);
	char s[N],ss[N];
	scanf("%s %s",s+1,ss+1);
	Knuth_Morris_Pratt(s,ss);
}