-
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을 사용하면 이분 그래프의 최대...
-
Bixby Studio
Bixby Studio Contents 빅스비 스튜디오란? 내가 만든 예제 발전 방향 참고 빅스비 스튜디오란? 우선 빅스비는 삼성전자에서 개발된 음성인식 기반 개인 비서 어플리케이션으로 현재 스마트폰 외에도 여러가지 기기(대부분의 삼성 디바이스)에서 사용되고 있다. 보통 빅스비는 현재 삼성 페이와 연결되어 쇼핑으로 자주 활용된다. 빅스비는 어떤 발화가 주어지면, 그 발화를 해결할 수 있는 캡슐을 검색하게 된다. 예를들어 어떤 장소에 대해 질문을 하는 발화가 주어졌다면, 장소를 찾는 캡슐을 검색하고 그 캡슐안으로 이동해서, 여러 지정된 액션들을 수행하게 된다. 예전에 빅스비가 나왔던...