-
Gumbel softmax
소개 언어 모델, 어텐션 메커니즘, 강화학습 등 다양한 문제에서 이산확률변수(discrete random variable)를 모델링해야 할 때가 있습니다. 하지만, 뉴럴 네트워크를 가지고 이러한 이산확률변수를 표현하는 것은 매우 어렵습니다. 왜냐하면 역전파(backpropagation) 알고리즘으로 미분 불가능(혹은 기울기가 0)인 레이어를 학습할 수 없기 때문입니다. 이러한 이산적인 연산을 sigmoid나 softmax 함수로 대체하는 것을 고려해 볼 수도 있습니다. 하지만, 이산적인 상태를 표현해야 하는 경우에는 이러한 함수를 사용할 수 없습니다. 또 다른 방법인 몬테카를로 방식으로 이산적인 연산의 gradient를 추정할 수 있지만 이 경우 큰...
-
APIO 2020
APIO 2020 올해 학생들 성적은 1금5은으로 예년과 비슷한 편으로 보인다. 반딧불이 300점 만점에 300점을 받아서, 2015년 이후 첫 APIO 만점과 함께 금메달을 얻었다. 반딧불 학생은 올해 IOI 국가대표이기도 한데, 아직 고등학교 1학년이니 앞으로도 좋은 결과가 기대된다. 그 뒤를 이어 이온조, 최서현, 장태환, 김지훈, 최은수 학생이 은메달을 얻었다. 모두 축하합니다! 1. 벽 칠하기 Subtask 1 (12점) 특정 벽을 칠할 수 있는 일꾼이 누구인지 고정되어 있다. 고로 색에 대해서 신경쓸 필요가 없고, 각 일꾼들이 문제의 조건에 맞게...
-
Understanding CRC
서론 작년 중순, 한 CTF에서 CRC와 관련된 문제가 하나 나왔습니다. 문제의 요지인 즉슨, flag{x}의 CRC 값이 다시 x가 나오게 하는 x를 구하는 것이었습니다. 이 과정에서 CRC의 특성에 대해서 이해하고 있는 사람이 별로 없다는 것을 알게 되었습니다. 또한 네트워크 수업에서도 Error code를 소개하는 자리에서 CRC가 나왔지만, CRC를 구하는 방법에 대해서만 알려줄 뿐 CRC가 어떠한 특성을 가지고 있는지는 알려주지 않았습니다. 최근에도 CRC에 대한 CTF 문제가 나오고 있고, 저도 CRC에 대해서 헷갈리던 부분이 있어서 이번에 한 번 정리하게...
-
A Generalized Birthday Problem
안녕하세요, 이번 글에서는 CRYPTO 2002에 소개된 David Wagner - A Generalized Birthday Problem 논문의 내용을 따라가며 논문에서 소개하는 Birthday Problem의 확장을 알아보겠습니다. Introduction Classic Birthday Problem Birthday Problem은 직관과 다르게 23명 이상만 있어도 그 중 두 명의 생일이 같을 확률이 1/2를 넘는다는 내용의 문제이고 별도의 설명이 필요한가 싶을 정도로 너무나 유명한 내용입니다. 암호학에서는 대표적으로 해쉬 함수가 N-bit이라고 할 때 해쉬값이 같은 두 입력을 찾기 위해서 $O(2^{N/2})$개의 입력에 대한 차분을 보면 된다는 정리가 Birthday Problem으로부터 도출되고...
-
General Matching and applications
General Matching and applications 유량(flow) 관련 알고리즘을 공부했다면 이분 그래프의 최대 매칭에 대해서는 익숙할 것이다. 이분 그래프에서 최대 매칭을 구하는 것은 크게 두 가지 의미에서 중요하다. 첫 번째는 문제 그 자체 에 대한 관심이다. 예를 들어, 택시 애플리케이션이 승객과 기사를 매칭하는 방법이나 결혼 중개업체가 남자와 여자를 짝짓는 방법 모두 이분 그래프의 매칭으로 표현할 수 있다. 두 번째는 이 문제가 다른 문제를 푸는데 어떻게 응용 될 수 있는지이다. 예를 들어, Konig’s theorem을 사용하면 이분 그래프의 최대...