-
프로그래밍 문제 출제하기
서론 삼성 소프트웨어 멤버십 블로그에는 대회 개최에 관한 글을 몇 개 찾아볼 수 있습니다. 대회 준비와 운영이 어떻게 진행되는지를 알 수 있는 유용한 글입니다. 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 등으로 양자 컴퓨팅 프로그래밍 언어를 사용할 수도 있습니다. 그러나 이런 시스템이 물리적인 양자 체계와...
-
P VS NP Question
P vs NP Question Contents 들어가며 P NP 란? 여러가지 NP문제들 PSPACE 와 NSPACE P = NP? 참고 들어가며 예전에 비해 프로그래밍이 좀 더 보편적인 분야로 자리잡으면서, 남녀노소 할 것 없이 많은 사람들이 프로그래밍을 접하고 있다. 또한 문제풀이로 알려진 Problem Solving 쪽을 많은 기업체 또는 학교에서 평가의 기준또는 test로 삼고 있다. 이러한 PS는 여러가지 분야가 있지만, 대부분이 주어진 제한적인 상황안에서 문제를 해결하게 된다. 보통 PS공부를 하기 위해서 알고리즘 공부가 필수라고 얘기한다. 그렇다면 알고리즘이란 무엇일까? 알고리즘을...
-
블루투스의 취약점들
1. Introduction 블루투스는 수많은 기기들이 근거리 통신을 위해 사용하는 프로토콜입니다. 컴퓨터와 연관이 있는 키보드, 마우스, 스피커 등의 입출력장치는 물론이고 심장박동수 측정 기기와 같은 의료기기들도 무선으로 정보를 송/수신해야할 필요가 있을 경우 블루투스를 사용합니다. 블루투스 통신에서 오가는 정보는 반드시 기밀이 유지되어야 하고 송/수신자가 아닌 외부의 공격자가 내용을 감청하거나 변조하는 일이 없어야 합니다. 그렇기 때문에 블루투스의 통신 규약을 보면 내용은 암호화가 되고 다양한 공격들에 대한 대비책을 미리 마련해두고 있습니다. 그러나 현존하는 모든 시스템이 그러하듯 블루투스 프로토콜도 다양한 취약점이...