-
고전 암호의 공격 기법
암호학에 대해 잘 알고 있나요? 암호학과 관련해 깊은 지식을 가지고 있지는 않더라도 분명 역사 속에서, 문학 속에서, 혹은 일상생활 속에서라도 암호학을 접해본 적이 있을 것입니다. 현대에는 컴퓨터의 성능이 비약적으로 발전했고 다양한 암호 분석 기법이 나왔기 때문에 단순히 각 알파벳을 다른 알파벳으로 치환하는 치환 암호 혹은 평문 내에서 글자의 순서를 바꾸는 전치 암호와 같은 고전 암호는 더 이상 사용되고 있지 않습니다. 그러나 실제로 개인이 고전 암호로 암호화된 메시지를 해독하려고 시도를 해본다면 설령 암호화 방식이 공개된 상태라고...
-
LiChao Tree (with Dynamic Segment Tree)
목표 LiChao Tree는 직선이 실시간으로 추가되는 Convex hull trick 문제를 해결하기 위한 자료구조입니다. 구현이 비교적 간단하면서 유용한 자료구조인데, 한글로 설명된 자료가 없어 포스트를 작성하게 되었습니다. 이 포스트의 목표는 LiChao Tree를 이용해 (백준 12795) 반평면 땅따먹기 문제를 해결하는 것입니다. 이 문제를 해결하는 방법은 다양하지만, LiChao Tree를 사용한 솔루션이 가장 수행시간이 빠릅니다. 사전지식 - Dynamic Segment Tree LiChao Tree는 Dynamic Segment Tree에 기반한 자료구조입니다. Dynamic Segment Tree란 구간의 범위에 따라 모든 노드를 만들어놓고 시작하는 일반적인 Segment Tree와는...
-
청개구리
청개구리는 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...