-
알고리즘 문제 judge program 만들기
안녕하세요? 저는 이번에 알고리즘 문제의 judge program을 만들어 보았습니다. 소스 코드와 input data, 그리고 output data가 있을 때 각각의 코드마다 어떤 테스트 케이스에서 어떤 결과가 났는지를 출력해주는 프로그램을 목표로 제작하였고, 이 글에서는 제가 만든 프로그램을 어떻게 구현했는지에 대한 간단한 소개를 진행해보도록 하겠습니다. 많은 online judge 사이트, 대표적으로 백준 온라인 저지나 codeforces, sw expert academy 등에서는 많은 문제를 제공하고, 채점 결과와 실행 시간, 메모리 사용량 등도 알 수 있지만 직접 만든 문제나 테스트케이스 등에 대해 확인해보는...
-
공개 키 암호화 시스템과 수학적 안전성
이 글에서는 공개 키 암호화 시스템이 발전해나가면서 같이 논의된 수학적 개념을 살펴보고자 합니다. 특히, 암호문으로부터 평문을 알아낼 수 없다는 막연한 속성을 수학적으로 어떻게 표현하는지 알아보고자 합니다. 목차는 다음과 같습니다. 공개 키 암호화 시스템 배경 지식 공개 키 암호화 시스템의 정의 Diffie-Hellman Key Exchange RSA 암호 One-wayness CPA Semantic Security and Indistinguishability Chosen Ciphertext Attack Random Oracle Model Malleability RSA-OAEP 마무리 각주 공개 키 암호화 시스템 공개 키 암호화 시스템Public Key Cryptosystem, PKC은 W. Diffie와 M....
-
프로그래밍 문제 출제하기
서론 삼성 소프트웨어 멤버십 블로그에는 대회 개최에 관한 글을 몇 개 찾아볼 수 있습니다. 대회 준비와 운영이 어떻게 진행되는지를 알 수 있는 유용한 글입니다. Acka1357님의 프로그래밍 대회를 개최하기 위한 10가지 djm03178님의 Codeforces #578, Codeforces #620 출제 후기 evenharder님의 UCPC 2020, KCPC 2018 출제 후기 hojoon0205님의 shake! 2019 출제 후기 이 글은 문제를 어떻게 만들 것인가에 초점을 둡니다. 아이디어를 어떻게 구상하고, 지문은 어떻게 작성하고, 데이터는 어떻게 만들고, 문제 검수는 어떻게 해야 하는지를 다룹니다. 백준 온라인 저지에...
-
Codeforces 레이팅의 경향 분석
서론 이전 글에서 Codeforces의 레이팅 계산법에 대해 다루어 보았습니다. 이번 글에서는 기존 라운드들에서의 통계를 이용하여 이 레이팅 체계가 어떤 경향을 보이고 있는지 살펴보고, 여기서 발견되는 구조적인 문제점의 원인을 분석해 보려고 합니다. 어떤 레이팅 시스템이 이상적이라면 각 참가자가 해당 라운드에서 기록한 ‘성적’에 따라 레이팅의 변화가 이루어져야 할 것인데, 많은 사람들의 경험에 의하면 특정 종류의 라운드에 참가하는 것이 다른 종류의 라운드에 참가하는 것에 비해 레이팅을 얻기가 훨씬 쉽다고 합니다. 이 현상이 어느 정도 심각한지를 집중적으로 조사해 보았습니다....
-
양자 컴퓨팅 - Surface Code
최근 양자 컴퓨팅의 error detection 및 correction에 사용되는 surface code의 기초를 잘 설명한 논문인 Surface codes: Towards practical large-scale quantum computation을 접했습니다. 이 포스트를 통해 양자 컴퓨팅에서 어떻게 error detection을 진행하고, surface code가 어떤 개념인지 설명하고자 합니다. 배경 지식 Shor’s Algorithm이나 Grover’s Algorithm 등의 양자 알고리즘이 개발되며 양자 컴퓨팅에 대한 관심이 커졌습니다. 2020년 현재 IBM Q Experience나 Amazon Braket, Microsoft QDK 등으로 양자 컴퓨팅 프로그래밍 언어를 사용할 수도 있습니다. 그러나 이런 시스템이 물리적인 양자 체계와...