각종 알고리즘
2020. 7. 8. 16:54ㆍPS/Problem Solving
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;
}
[프림]
아래 링크 보고 공부하는 거 추천
#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);
}
728x90
'PS > Problem Solving' 카테고리의 다른 글
Counting Sort할 때 누적합 배열 사용 이유 (0) | 2020.07.22 |
---|---|
[백준] 퇴사 (0) | 2020.07.20 |
세종 병원 (0) | 2020.06.22 |
첫 Codeforces (0) | 2020.06.17 |
시험 끝나고 PS (1) | 2020.05.31 |