-
Dynamic MSF with Subpolynomial Worst-case Update Time (Part 1)
Dynamic MSF with Subpolynomial Worst-case Update Time (Part 1) 그래프에서 최소 스패닝 트리 (Minimum spanning tree)를 구하는 문제는 아주 잘 알려져 있고, 일반적으로 가장 처음 공부하게 되는 그래프 알고리즘에 속하며, 매우 다양한 개념에 응용된다. 그래프의 최소 스패닝 트리는 크루스칼 알고리즘을 통해서 $O(m \log m)$ 에 효율적으로 구할 수 있다. 하지만 그래프에서 간선이 추가되고 제거되는 등의 업데이트가 가해진다면, 이 알고리즘은 매 갱신마다 전체 간선 리스트를 전부 순회해야 하니 더 이상 효율적이지 않게 된다. 이렇게 그래프의 일부가...
-
Codeforces Round #688 개최 후기
개요 Codeforces Round #688 (Div. 2) Announcement Editorial (이전 글) Codeforces Round #620 개최 후기 (이전 글) Codeforces Round #578 개최 후기 올해 초 Codforces에서 개최했던 620번 라운드는 제게는 잊을 수 없는 기분 좋은 추억입니다. 처음으로 단독 출제자를 해본 대회에 무려 14612명이 등록해서 좋은 반응을 이끌어냈었다는 것이 정말 좋았습니다. 그 기분을 다시 느끼고 싶어서 라운드가 종료되고 얼마 지나지 않아 바로 다음 라운드를 준비하기 시작했고,1 12월 4일 22시 05분(KST)부터 2시간 15분에 걸쳐 Codeforces Round #688 (Div....
-
IOI 2020 및 SNUPC 2020 출제후기
SNUPC 2020 출제후기 SNUPC 2020에는 Div.1의 총 9문제중 절반 정도에 해당하는 4문제를 출제하였다. 재미있는 문제를 낼 수 있어서 만족스러웠다. 그리고 imeimi2000, TAMREF 등 여러 출제진 검수진들이 고생해 준 덕분에 문제 데이터와 지문의 퀄리티가 올라가서 성공적인 대회가 될 수 있었던 것 같다. 9문제 중 대부분이 자명하지 않고 아이디어를 필요로 하는 문제들이라서 아직 풀어보지 않은 분들은 시도해 보고 나서 글을 보면 좋을 것 같다. 자세한 풀이는 여기 에 있으니 여기에는 담지 않는다. A. 빈 문자열 만들기 링크...
-
Post-Quantum Cryptography
1. Introduction 양자 컴퓨터가 언제 상용화가 가능할지는 예측이 힘들지만 양자 컴퓨터의 개발 이후 영향을 받을 분야는 굉장히 많고 그런 분야들에서는 관련 연구를 활발하게 진행하고 있습니다. 한편 양자 컴퓨터의 이론적 개념은 양자 역학과 컴퓨터 과학에서의 계산 이론 분야의 깊은 이해를 요구하기 때문에 (저를 포함한) 많은 사람들은 양자 컴퓨터의 개념을 매우 피상적으로 알고 있거나 기능을 잘못 이해해서 양자 컴퓨터가 상용화되면 모든 암호 체계가 붕괴된다고 착각하는 경우가 종종 있습니다. 이번 글에서는 양자 컴퓨터 시대를 대비하는 Post-Quantum Cryptography에 대해...
-
Sudoku and Nonogram with z3
서론 이전에 z3와 Boolector를 비교하는 글을 올린 적이 있습니다. (Link) 그런데 정작 z3에 대해서 글이 잘 없어서, 이번에 z3로 퍼즐을 푸는 글을 작성해보게 되었습니다. 스도쿠는 이미 충분히 유명하고, 노노그램은 네모네모 로직이나 피크로스 등을 통해서 많은 분들이 알고 계신 퍼즐이기 때문에 고르게 되었습니다. 이번 글에서는 스도쿠랑 노노그램의 솔버를 하나씩 설명해가면서 작성해보려고 합니다. 본론 Sudoku 스도쿠는 9x9개의 정수를 맞추는 퍼즐 게임입니다. 정수는 모두 1부터 9로 구성되며, 9x9개의 정수 중 몇 개의 값이 고정되어 있습니다. Wikipedia에 있는 sudoku...