문자열 - 아호 코라식(Aho-Corasick)
아호 코라식(Aho-Corasick)에 대해 알아보자.
뭔가 엄청나게 오랜만의 포스팅이다.
이 글의 주인공은 이번 방학동안 참여한 알고리즘 캠프이다.
나는 지난 3학기동안 꾸준히 신촌엽합의 캠프를 들었고 suapc는 2학기동안 참여했다.
하지만 후기를 쓰는 것은 처음이다. 항상 이 캠프가 끝나면 학기가 시작되니 귀찮음을 이겨내지 못했던 것이다.
이번엔 꽤나 만족할만한 결과를 거두기도 했고 월공강이라 여유도 생겼으니 여름캠프와 suapc둘다 여기에 후기를 남겨볼 것이다.
이번이 3회차인 캠프인데 이번 캠프는 지난 두 차례와 많이 달랐다.
일단 난이도가 쉬워졌다. 이는 매우 좋다고 생각한다. 알고리즘에 시간투자를 많이 하지 않는 사람들 (나는 아니지만)도 문제들을 건드려 볼 수 있고 열심히 하는 사람들이 조금 여유를 가질 수 있게 해준다.
그래서 이번 캠프를 하면서는 내 개인적인 시간에 게임도 할 수 있고 다른 문제들도 풀어 볼 수 있었다. 저번캠프에서는 하루종일 풀어도 못푸는 문제도 많았었다.. 물론 내 실력이 는 이유도 있겠지만 난이도 하락은 캠프의 진입장벽을 낮춰주어 좋았다.
그리고 환급 시스템이 거의 대부분의 돈을 환급받을 수 있어서 좋았다. 나처럼 시간투자를 많이하는 사람에게는 공짜로 이런 좋은 캠프를 참여할 수 있다는 것이 너무 좋았다.
마지막으로 이번엔 조금 난이도가 쉬워진 대신 일정이 빡빡해졌다. 이전의 캠프들은 주에 2회정도 했었는데 이번엔 주 3회로 약간 빡빡한 일정이었다. 하지만 난이도가 쉬워져서 그런지 오히려 실전 압축같고 좋았다.
이번 캠프는 상당히 쉬워졌다고 느끼지만 그래도 사람들이 많이 풀지 않는다고 생각한다.
캠프 참여인원이 30명 정도라고 하면 실제로 열심히 푸는 사람들은 5~6명정도 된다.
막히는 문제가 생기면 놓고 싶어지는 것은 알지만 30분에서 1시간 사이로 고민하다가 질문을 하거나 인터넷을 조금 참고해도 된다고 생각한다. 모르고 포기하는 것보다 누군가 떠먹여 주더라도 해결을 하는것이 좋다고 생각하기 때문이다.
알고리즘에 인생을 갈아넣긴 어려운 사람들도 많지만 그래도 열심히하는 사람이 더 많아졌으면 좋겠다.
나는 생각보다 잘한다.
코드포스를 하다가 블루가는 것을 실패하고 절망하고, 최근에 ucpc에 나가서도 1문제도 풀지 못해 팀에게 기여하지 못해서 마음이 힘들었었다. 그래도 여기서 문제를 풀면서 깔끔하게 풀기도 하고 사람들이 내 코드를 구경해주기도 하면서 자신감을 얻었다.
누구든지 PS(problem solving)를 하다보면 절망할 때가 있다고 생각한다. 하지만 꾸준히 한다면 결코 실력이 떨어지지는 않는다. 그리고 PS를 하는 사람들은 매우 열심히 하는 사람들이 많고 그 분들이 많이 보이기 때문에 상대적으로 내가 못해보이는 것이다. 어쩌면 평범한 사회에는 PS의 존재를 아는 사람이 더 적을지도 모른다. 백준의 존재를 아는 우리는 이미 상위 1%아닐까싶다.
이번 캠프를 하면서 꾸준히 하는 나를 보며 나는 생각보다 잘한다는 것을 느꼈다.
처음 참가했던 캠콘에서는 7등 → 2번째는 3등 → 이번에는 2등으로 점점 발전했다!! (다음엔 1등??)
2등이라서 기분 좋은것도 있지만 점점 발전하는 나의 모습에 기분이 너무 좋았다.
거기다가 신촌연합에 있는 대학들 (연대, 서강대, 이대, 숙대) 모두 너무 잘하는 대학들이라 이 사이에서 내가 발전했다는 것은 정말 기분좋은 일이다.
솔직히 문제는 예전 캠콘에 비해서 1e9+7배는 쉬웠다. 이전에는 건드리지도 못하는 문제들이 막 3개씩 있었는데..
이번에는 딱 한문제만 못 건드렸다. 나머지는 다 풀었다!!
조금 아쉬운점은 페널티관리를 너무 못했다. 특히 B번에서 테스트하려고 범위를 작게 설정했던것을 그대로 제출했다거나, A번 실수오차를 3번정도 냈다거나, F번 시작할 땐 무조건 통과한다는 것을 까먹었다거나 , 자잘한 실수들은 앞으로 천천히 고쳐 나가봐야겠다.
또 아쉬운점은 마지막문제 제출이라도 해서 스코어보드에 긴장감을 불어넣지 못한 점이 아쉽다. ㅋㅋㅋ 뭔가 예제도 제대로 안나오니 제출하기 싫었나보다… 그래서 약간 김빠지는 스코어보드 개봉이 되었다.
어쨋든 매우 만족스러운 결과를 냈고, 나에게 이런 즐거운 경험을 준 신촌 연합에게 감사하다. (홍대에 오길 잘했다는 생각도 들었다.)
이번 대회는 감사하게도 학교 후배들인 동현이(mastershim)와 승민이(smjun04)가 같이 팀을 해보자고 해서 함께하게 되었다. 실력이 좋은 친구들이라 좋은 성적을 거둘 수 있을거라고 생각했고 목표는 5등안이였다. (당연히 무리수인 목표인데 목표는 높게 잡아야 하니까!!)
팀이름은 홍하예프로 했고 홍대생 밈을 그냥 쓰고싶어서 쓴 것이다.
이 대회에 출전하기전 ucpc도 참여해보고, 서강대에서 했던 icpc연습도 참여했는데 그 때마다 내가 너무 못해서 미안했다. 그래서 이번대회에서는 꼭 밥값을 해야지라고 생각했었다.
결과는 수상컷이었다. (6솔로 10등을 했다)
그래도 상위권 팀들과의 차이는 솔직히 많이 느꼈다. 6솔을 빨리해서 다행이었다.
나는 I번과 L번을 풀었고 J번 마지막에 구현해둔 코드 보여주는 정도의 기여를 했다.
L번은 우선순위큐 11개만드는 매우 쉬운문제였고, I번은 포함배제 원리를 이용한 것이였는데 dp를 곁들여서 풀었다.
I번은 솔직히 좀 어려운데 잘 푼것 같아서 기분이 매우 좋다.
아쉬운점은 D번을 실패했다는 점, 아이디어는 맞았는데 구현을 못했다는 것이 너무 아쉽고,
F번 생각을 안했다는 점, 게임이론 + kmp인것을 파악했지만 kmp를 어떻게 써야하지 고민을 10분도 안해보고 포기를 했다는게 너무 아쉽다.
9등인 우진스 팀에게 그 차이로 밀린것이 분했다!!!
그래도 우리팀의 첫 출전인데 수상권에 든 기염을 토했다는 것은 참 뿌듯했다. (나도 꽤 기여를 한 것 같고)
다음에도 신촌연합의 캠프를 참여할지는 미지수이다. 이 캠프가 싫어서가 절대 아니다. 다만 알고리즘에 시간투자를 너무해서 다른것을 너무 못했다는 것이 문제다.
하지만 후배들이 이 캠프를 고민한다면 나는 주저없이 추천할 것이다.
훌륭한 친구들이 옆에서 푸는 것을 보며, 경쟁하며, 같이 문제를 고민하는 것은 매우 도움이 되기 때문이다.
방학을 알차게 보내게 해주어서 감사하다. 나는 이제 여유롭게 문제를 풀며 코드포스 블루를 다시 도전해보려고 한다.
아호 코라식(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