문자열 - 아호 코라식(Aho-Corasick)
아호 코라식(Aho-Corasick)에 대해 알아보자.
[4803 트리] https://www.acmicpc.net/problem/4803 .
상호 배타적 집합(disjoint set)을 이용하여 트리인지 아닌지 판단한다.
정점을 잇는 간선이 주어진다 .
이 그래프는 서로 떨어져있는 그래프일 수도 있고 사이클이 있을 수도 있다.
즉 떨어져 있는 그래프 하나 하나가 트리인지 아닌지 확인하고 그 개수를 세는 것이다! 트리의 특징으로는 정점이 V면 간선의 개수는 v-1이고, 사이클이 없다는 것이다.
집합을 다루는 자료구조이다.
각 집합마다 부모가 하나 있다고 하고 이를 트리 구조로 정리하는 것이 disjoint set이다.
이 문제에서는 merge부분을 조금 변형하여 disjoint set을 구현했다.
disjoint set기본 자체는 종만북 : 알고리즘 문제해결 전략을 참고하였다.
struct disjointSet{
vector<int> parent,rank;
disjointSet(int n):parent(n+1), rank(n+1, 1){
for(int i=1;i<=n;i++) parent[i] = i;
}
int find(int u){
if(parent[u]==u) return u;
return parent[u] = find(parent[u]);
}
void merge(int u, int v){
u = find(u);
v = find(v);
if(u==v){
tominus[v] = 1;
return;
}
if(tominus[u]&&tominus[v]) tominus[u] = 0;
if(rank[u]>rank[v]) swap(u,v);
parent[u] = v;
rank[v] += rank[u];
rank[u] = 0;
}
};
사이클이 있는 것도 세어주되 나중에 빼주기 위해서 위에 있는 tominus 배열을 만들었다.
연결되어있는 그래프의 개수를 모두 세고 그중에 tominus(사이클이 있는 그래프)를 빼준다는 느낌이다.
하지만 문제가 생겼다!! 사이클이 있는 두 개의 집합을 합칠 때 tominus가 각각 1이라서 총 2번 빠지는 문제가 생겼다.
이는 둘다 tominus가 1인것을 합칠 때 하나를 0으로 만들어 줌으로써 해결했다.
반례를 만들었으니 참고 하면 좋을것 같다.
9 13
1 2
2 3
3 4
1 5
2 5
3 5
4 5
6 7
7 8
8 9
6 9
7 9
4 6
0 0
답은 no tree여야하는데 나는 tree값이 음수가 되어버려 이상한것을 출력했다..
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> tominus;
struct disjointSet{
vector<int> parent,rank;
disjointSet(int n):parent(n+1), rank(n+1, 1){
for(int i=1;i<=n;i++) parent[i] = i;
}
int find(int u){
if(parent[u]==u) return u;
return parent[u] = find(parent[u]);
}
void merge(int u, int v){
u = find(u);
v = find(v);
if(u==v){
tominus[v] = 1;
return;
}
if(tominus[u]&&tominus[v]) tominus[u] = 0;
if(rank[u]>rank[v]) swap(u,v);
parent[u] = v;
rank[v] += rank[u];
rank[u] = 0;
}
};
int main(){
cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
int tc=0;
while (1){
tc++;
int n, m;
cin >> n >> m;
if(n==0&&m==0) break;
tominus = vector<int> (n+1,0);
disjointSet dset(n);
int trees = 0;
for(int i=0;i<m;i++){
int a,b;
cin >> a >> b;
dset.merge(a,b);
}
for(int i=1;i<=n;i++){
if(dset.rank[i]>0) trees++;
trees -= tominus[i];
}
if(trees==0) cout << "Case " << tc << ": No trees." << '\n';
else if(trees==1) cout << "Case " << tc << ": There is one tree." << '\n';
else cout << "Case " << tc << ": A forest of " << trees << " trees." << '\n';
}
}
아호 코라식(Aho-Corasick)에 대해 알아보자.
docker를 이해해보자
2060 염소줄서기 풀이 및 코드
분할정복을 이용한 다이나믹 프로그래밍 최적화
코드포스 다시 열심히! 블로그도 열심히!
rust 공부시작!
코드포스 블루 달성 후기
여름캠프 및 SUAPC 후기
2023-05-25-Edu Codeforce round 149 (Div.2)
2023-05-13-Edu Codeforce round 148 (Div.2)
HLD(Heavy Light Decomposition)
행렬 거듭 제곱
2023-05-02-It takes two
Codeforce round 868 (Div.2)
2월 11일 문제풀이
Codeforces#846, TypeDB Foreces 2023, Codeforces#848 업솔빙
ps5 게임 : 용과같이 제로 리뷰
백준 23877번 Convoluted Intervals 문제풀이
codeforce round #828(div 3), EDU #137(div 2) 업솔빙
codeforce round #823(div 2), #824(div 2) 업솔빙
AtCoder Beginner Contest 270 업솔빙
ps5 게임 : 용과같이 극 1 리뷰
백준 18719번 Binomal 문제풀이
백준 14288번 회사문화4 문제풀이
백준 3308번 Matching 문제풀이
백준 18186번 라면사기(large) 문제풀이
백준 4196번 도미노 문제풀이
백준 3176번 도로 네트워크 문제풀이
백준 16367번 TV Show Game 문제풀이
ps5 게임 : 페르소나 5 더 로열 리뷰
codeforce round #811(div 3), #812(div 2), CodeTon round 2 업솔빙
백준 21162번 뒤집기 K 문제풀이
codeforce round #808(div 2), #803(div 2, virtual) 업솔빙
codeforce round #807(div 2) 업솔빙
백준 10167번 금광 문제풀이
codeforce round #805(div 3), #806(div 4) 업솔빙
백준 18253번 최단경로와 쿼리 문제풀이
에듀 라운드 131 업솔빙
백준 1949번 우수 마을 문제풀이
백준 3665번 최종 순위 문제풀이
Trie 자료구조 이해하기
merge sort를 이용하여 inversion 개수세기
3솔의 벽이 너무 높다..
lazy propagation없이 구간 갱신하기
코드포스 폭망기념 upsolving
백준 11505 구간 곱 구하기 문제풀이
백준 1305 광고 문제풀이
백준 4386 별자리 만들기 문제풀이
백준 4803 트리
백준 2206 벽 부수고 이동하기 문제풀이
백준 2166 다각형의 면적 문제풀이
백준 12015 가장 긴 증가하는 부분 수열2 문제풀이
백준 10986 나머지합 문제풀이
스택 구현하기 ========== 자료구조의 기본이라고 하면 스택 과 큐가 있다 백준 10828번에서 마주친 스택
매우매우 많은 정렬이 있지만 그중 가장 안 어려운 3가지를 공부해보았다.
Leave a comment