PS 이야기

문제: http://www.ioi2011.or.th/hsc/tasks/KOR/elephants.pdf대회 당시 이 문제에 상당히 많은 시간을 투자했다. 시간제한이 9초라는 것을 간과하고 단지 N 제한이 크다는 이유 만으로 해법이 $O(N lg N)$ 꼴로 나올 것이라 확신했었다. 부분 점수를 받기 위해 $O(N\sqrt{N})$ 꼴의 방법도 생각해보았지만, 실패했었다.대회 끝나고 나오자마자 당시 조교로 있었던 권순일 형의 짧은 말로 이 문제의 해법을 깨닫게되었다. 2년이 지난 지금까지도 기억에 남는다. 시간복잡도는 $O(N\sqrt{N})$ 이 맞다. 안된다고 생각할 수 있지만, $\sqrt{N}$ 번의 update 마다 새로 그룹들을 $O(N)$만에 구성해주면된다. 그러면 총 시간복잡도를 $O(N\sq..

문제: http://www.ioi2011.or.th/hsc/tasks/KOR/crocodile.pdf우선, 0번 방에서 탈출 방에서 가는 것이 아닌, 탈출방에서 각 방으로 가는 방향으로 뒤집어 생각해야한다. $$D[i] = 악어문지기가\ 최선을\ 다\ 할때,\ 임의의\ 탈출방에서\ i번\ 방으로\ 오는\ 최소\ 시간$$D[i] 를 위와 같이 정의하자. D[i]는 i번 방으로 올 수 있는 방들 중에 D[j]+(j번 방에서 i번 방으로 이동하는 시간)이 2번째로 작은 값을 취해야한다. 이를 해결하기 위해서는 $O(N^2)$ 방법과 $O(N lg N)$ 방법이 존재한다.$O(N lg N)$ 방법은 힙(heap)을 이용해 다잌스트라(Dijkstra's Algorithm)를 돌리듯이 하면 된다.코드: http:/..

초등학교 3학년 때 간단하게 html 코딩하면서 홈페이지 만드는 것을 좋아했었다. 그 때 부모님을 겨우겨우 설득해 myungwoo.net 으로 도메인을 만든적이 있었다. 당시에 물론 나 혼자 좋아하고 놀기 위해 만들었었지만, 도메인이 어떻게 구성되어 있는지 이론은 아무것도 모른채, http://myungwoo.net 에 접속했을 때 내 홈페이지가 뜨는 것에 마냥 신기해 했다.정확히 10년이 지난 지금, 10년 전과는 많이 발전한 목적으로 도메인을 구매했다. 항상 나만의 도메인을 가지고 싶다고 생각했었고, 성인이 된 지금 2만원가량의 결제를 망설일 이유가 있을까... 어렸을 때 도메인을 구매했을 때 처럼 마냥 신난다.예전에 쓰던 .net 이 아닌 10년 전에는 존재하지 않았던 .kr 을 쓰기로 했다. 그리..