구사과

ICPC 월드 파이널 2017 주간이 다가와서 최근 옛날 기출문제를 풀어보고 있다. World Finals 2008도 opencup 팀연습으로 돌았었는데, 문제가 좋다는 느낌은 안 들었다. 특히 어려운 문제들이 찍어 맞춰라 / 단순 코딩 지옥이라 불만족스러웠음.이번 ICPC에서 한국 팀들의 성적이 그 전과 비교가 안 될 정도로 우수하다. 어느 정도 훌륭할 것이라고 예상은 했지만 이 정도일 것이라고 예상한 사람은 아무도 없었을 것이다. 팀원들이 대부분 젊은데, 앞으로도 많은 활약을 기대해 본다. 2011 G. Magic Sticks일단 모든 막대기를 사용해야 하는 상황이라고 가정해보자. 넓이를 최대화하려면 모든 정점을 원 위에 뿌려주는 것이 최선이다. 직관적으로 그럴듯 해 보이긴 하는데 증명은 음.. 암튼..

(Stankonia, 2000)

https://www.slideshare.net/ssuser81b91b/ahocorasick-algorithm 문자열 S와 여러 개의 문자열 T가 주어졌을 때, T에 있는 문자열 중 하나와 S가 매칭이 되는 지를 계산 할 수 있는 알고리즘이다. 선형 시간에 작동한다.Aho Corasick Algorithm을 알기 위해서는 KMP 알고리즘과 트라이에 대한 이해가 필요하다. KMP 알고리즘에 대한 koosaga.com의 설명 아호 코라식 알고리즘을 한 문장으로 설명하면, KMP에서 사용하는 Failure function을 트라이에 확장시키는 것. 딱 이것으로 끝난다. 스텝도 비슷하다. * 1. 트라이가 주어졌을 때 트라이에서 Failure function (Failure link나 Suffix link라고도..