문자열 - 아호 코라식(Aho-Corasick)
아호 코라식(Aho-Corasick)에 대해 알아보자.
이쯤 되면 컨디션 문제도 아닌것같다.
내가 그린은 어케 갔었는지도 의문이다.ㅋㅋㅋㅋㅋ
코포는 시간이 생명인데 영어에서 자꾸 절어서 시간이 오래걸리고 여전히 3솔을 못한다.ㅠㅠ
이제부턴 진짜 버추얼이라도 돌아봐야겠다.
너무 쉬웠는데 한번 틀렸다.
영어를 잘못 이해했다. 자신을 포함해서 총 3개의 칸이 지워지는건데 왜 2개라고 읽었는지 모르겠다.
바보 같은 실수로 절고 7분 걸렸다.
int cnt=0;
for(int i=0;i<2;i++){
for(int j=0;j<2;j++){
cin >> board[i][j];
if(board[i][j]) cnt++;
}
}
if(cnt==4) cout << 2 << '\n';
else if(cnt==0) cout << 0 << '\n';
else cout << 1 << '\n';
이거는 해석을 오히려 잘해서 헷갈렸다.
해석한 걸로 따지면 d가 2일 때가 최적이고 그냥 그걸 출력하면 된다.
그러면 d가 의미가 있나 싶어서 말도 안되는 증명하다가 시간 다 보냈다.
그래서 2틀하고 에라이 그냥 d가 2인걸로 하자 했더니 AC나옴..ㅡㅡ
cout << 2 << '\n'; //d는 무조건 2가 최적
for(int i=1;i<=n;i++){
if(visited[i]) continue;
for(int j=i;j<=n;j*=2){
if(visited[j]) continue;
cout << j << ' ';
visited[j] = true;
}
}
솔직히 많이 배운 문제이다.
처음에는 dp인가 하다가 아닌것같아서 다시 생각해보니
[이중 우선순위 큐] https://www.acmicpc.net/problem/7662 .
가 생각났다. 그래서 우선순위 큐 2개로 다뤄봤는데 디버깅하다가 우선순위큐가 중복을 허용하지 않는다는 걸 알았다.
그래서 멘붕왔는데 내 풀이를 버리질 못하고 서성대다가 끝나버렸다.
다른분들중에 나랑 같은 생각하신 분은 multiset을 이용하여 풀었더라…
멀티셋을 활용하는걸 잘 알아둬야겠다.
에디토리얼에는 이분탐색으로 푸는 방법이 나와있고 내가 이분탐색을 매우 못한다는 것을 깨달았다.
bool check(int t){
ll fr =0, need = 0;
for(int i=1;i<=n;i++){
if(t>=nums[i]) fr += (t-nums[i])/2; //자기 일 끝내고 남는 시간
else need += nums[i] -t; // 자기 일을 못끝내서 남는 시간
}
return need<=fr; //시간이 여유로우면 참을 리턴
}
int l = 0, r = 2*m; // 모든일을 2시간이 걸려서 하면이 최대고
int res = -1;
while (l<=r){ //이분탐색으로 제일 여유로운 시간중 최솟값을 찾는다
int mid = (l+r)>>1;
if(check(mid)){
res = mid;
r = mid-1;
}else{
l = mid+1;
}
}
cout << res << '\n';
나에겐 넘 어려웠다 어떤 상황인지는 알겠는데 아이디어가 진짜 안 떠올랐다.
그래서 10분보고 그냥 버렸던 것 같다.
핵심은 수학적으로 처음 배열과 수정된 배열의 관계를 알아내는 것이다.
그러면 범위가 나오고 그 범위의 시작점이 작으면서 끝점도 작은 것 부터 해결한다.
에디토리얼을 보고도 굉장히 까다로웠던 문제였다.
original = vector<int> (n+1);
modify = vector<int> (n+1);
seg = vector<pii> (n+1, make_pair(-1, -1));
for(int i=1;i<=n;i++) cin >> modify[i];
for(int i=1;i<=n;i++){
seg[i] = make_pair(i/(modify[i]+1)+1,i); //i번째 idx의 수는 i/modift[i]+1 이상이다
}
sort(seg.begin(), seg.end());
int j =1;
set<pii> s;
for(int i=1;i<=n;i++){
while (j<=n&&seg[j].first==i){
int idx = seg[j++].second;
s.insert(make_pair(modify[idx]?idx/modify[idx]:n, idx)); //idx번째 수는 first이하이다.
}
original[s.begin()->second] = i;
s.erase(s.begin());
}
for(int i=1;i<=n;i++) cout << original[i] << ' ';
cout << '\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