-
청개구리
청개구리는 2004년 한국정보올림피아드 지역본선에서 가장 어려운 문제인 고등부 5번으로 출제된 문제이다. 일단 국내 대회의 기출 문제이고, 문제 내용도 어렵지 않고 입력되는 값의 범위도 작아서 많은 사람들이 관심을 갖고 해결을 시도해 왔다. 하지만 오랜 기간 동안 그 누구도 맞았습니다!!를 받지 못했고1, 문제나 데이터가 잘못되었다는 의문을 제기하는 사람도 적지 않았다. 그러나 2018년 4월 본인을 포함해 두 명의 맞은 사람이 나오면서 문제에는 이상이 없는 것으로 밝혀졌고 이 문제는 Baekjoon Online Judge에서 가장 신비로운 문제의 대명사가 되었다. 이 문제의...
-
Segment Tree를 활용한 2D Range Update/Query
이 포스트는 Nabil Ibtehaz, Mohammad Kaykobad, Mohammad Sohel Rahman의 Multidimensional segment trees can do range queries and updates in logarithmic time 논문에서 핵심 아이디어를 가져와 작성한 것입니다. 독자가 1/2차원 세그먼트 트리와 Lazy propagation에 대한 지식을 알고 있다고 가정하고 글을 작성합니다. 아래에 제시된 코드는 모두 Kotlin으로 작성하였습니다. 목표 이 글의 목표는 2차원 세그먼트 트리를 이용해 $n \times m$ 크기의 2차원 배열 $A$에 다음과 같은 연산을 $O(\log n \log m)$ 시간에 수행하는 것입니다. Update: 모든 $(x, y)...
-
markdown text
Advertisement :) pica - high quality and fast image resize in browser. babelfish - developer friendly i18n with plurals support and easy syntax. You will like those projects! h1 Heading 8-) h2 Heading h3 Heading h4 Heading h5 Heading h6 Heading Horizontal Rules Typographic replacements Enable typographer option to see result. (c) (C) (r) (R) (tm) (TM) (p) (P) +- test.. test… test….. test?….. test!…. !!!!!! ???? ,, – — “Smartypants, double quotes” and ‘single...