문자열 - 아호 코라식(Aho-Corasick)
아호 코라식(Aho-Corasick)에 대해 알아보자.
[4386 별자리 만들기] https://www.acmicpc.net/problem/4386 .
간선을 추려서 MST(minimum spanning tree)를 만든다.
정점들의 위치가 주어지고 이동은 어디든 할 수 있다 .
이동 할때 그 거리는 점과 점사이의 거리이다.
모든 별이 연결은 되어 있어야한다.
즉 후보 간선들을 만들고 모든 점을 포함하는 MST를 만들고 그 가중치들을 다 합하면 끝이다!
minimum spanning tree.
그래프는 여러가지 스패닝 트리를 만들 수 있는데 그중 가중치 합이 가장 작은 트리이다.
그래프의 연결성은 유지하고 가장 싼 그래프를 찾는 것이다.
이를 찾는 대표적인 알고리즘으로 Kruskal 알고리즘과, Prim알고리즘이 있다.
잘 알려진 구현방법으로 하면 Kruskal은 O(ElogE), Prim은 O(VE)이다.
오늘은 E가 약 10000까지 커질 수 있고 V는 최대 100이다. 둘 중 무엇을 써도 되지만 프림 알고리즘을 최적화하여 O(ElogV)로 문제를 풀어보겠다.
각 정점에서 간선은 V-1개만들 수 있다 이를 다 만들고 검사해도 시간안에 잘 통과 할 것이다.
getDist함수를 짜서 이를 이용해 간선을 만들어보자.
//거리를 구하는 함수
inline double getDist(pdd p1, pdd p2){ //함수 호출엔 시간이 오래걸리니 inline함수로 선언했다.
double temp = pow((p2.first-p1.first), 2)+pow(p2.second-p1.second, 2);
return sqrt(temp);
}
// 구한거리를 가중치로 하여 간선들 정보 저장하기
for(int i=0;i<n;i++){ //각각 자신을 제외하고 n-1개의 간선을 갖는다. 간선 수의 최댓값은 10000
for(int j=0;j<n;j++){
if(i==j) continue;
adj[i].push_back({getDist(stars[i], stars[j]),j});
}
}
실수 연산이므로 출력형식에 주의해야한다.
프림알고리즘을 최적화하는 과정이 다익스트라와 비슷하지만 다익스트라는 한 정점에서의 최단거리를 구하는 거라면
프림알고리즘은 각 정점에서 최단거리만 뽑아서 검사하는 것이다.
매우 비슷하게 생겨서 주의를 해야한다
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
typedef pair<double, double> pdd;
typedef pair<double, int> pdi;
const int INF = 987654321;
int n;
vector<pdd> stars;
vector<pdi> adj[101]; //가중치가 있는 인접리스트
inline double getDist(pdd p1, pdd p2){
double temp = pow((p2.first-p1.first), 2)+pow(p2.second-p1.second, 2);
return sqrt(temp);
}
double prim(){
vector<bool> intree(n, false);
vector<double> minweight(n, INF);
double ret = 0;
minweight[0] = 0;
priority_queue<pdi, vector<pdi>, greater<pdi> > pq;
pq.push({0, 0});
while (!pq.empty()) {
int here = pq.top().second;
double weight = pq.top().first;
pq.pop();
if(intree[here]) continue;
intree[here] = true;
ret += weight;
for(int i=0;i<adj[here].size();i++){
int there = adj[here][i].second;
double togo = adj[here][i].first;
if(!intree[there]&&minweight[there]>togo){
minweight[there]= togo;
pq.push({minweight[there], there});
}
}
}
return ret;
}
int main(){
cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false);
cin >> n;
for(int i=0;i<n;i++){
double y, x;
cin >> y >> x;
stars.push_back({y,x});
}
for(int i=0;i<n;i++){ //각각 자신을 제외하고 n-1개의 간선을 갖는다. 간선 수의 최댓값은 10000
for(int j=0;j<n;j++){
if(i==j) continue;
adj[i].push_back({getDist(stars[i], stars[j]),j});
}
}
cout << fixed;
cout.precision(2);
cout << prim();
}
아호 코라식(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