-
PS에서의 런타임 에러와 디버깅
서론 알고리즘 문제를 온라인 저지에서 풀다 보면 다양한 종류의 채점 결과 (verdict)를 받게 됩니다. 백준 온라인 저지의 경우 통상적으로 볼 수 있는 채점 결과만 ‘맞았습니다!!’, ‘틀렸습니다’, ‘시간 초과’, ‘메모리 초과’, ‘컴파일 에러’, ‘런타임 에러’, ‘출력 초과’, ‘출력 형식이 잘못되었습니다’ 등 8가지나 됩니다.1 그런데 애석하게도 이 중에 좋은 결과는 오로지 ‘맞았습니다!!’ 하나뿐이고, 나머지는 모두 안 좋은 결과입니다. 이 안 좋은 결과들의 의미는 대부분 명확합니다. ‘틀렸습니다’는 말 그대로 출력 내용이 정답이 아니었던 것이고, ‘시간 초과’는 말 그대로...
-
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으로부터 도출되고...