-
evenharder's profile image
evenharder
January 22, 2021
'촛불과 그림자' 해결 일지
혹시 기하 문제를 좋아하시나요? Problem Solving에 나오는 어려운 기하 문제는 다양한 예외처리와 기하 문제 특유의 방향성 때문에 인해 일반적으로 기피대상입니다. 우연히 맞닥뜨린 문제인 BOJ 18190번 ‘촛불과 그림자’도 악명 높은 기하 알고리즘 문제로, solved.ac에서 Ruby V로 평가되는 고난이도의 문제입니다. 알고리즘 구상부터 해결까지 대략 일주일 정도 걸린 시련의 길을 반면교사로 삼고자 이렇게 글을 쓰게 되었습니다. 이후엔 촛불과 그림자 문제의 상세한 아이디어와 풀이가 나오므로 유의하시기 바랍니다. ‘촛불과 그림자’란? 해결 일지 1월 14일: 구상 1월 15일: 첫 제출에서 59%까지...
-
evenharder's profile image
evenharder
December 20, 2020
대화형 증명 시스템과 영지식 증명
이전 글에서는 공개 키 암호화 시스템에서 보안을 어떻게 챙겨야 하는가를 다루었습니다. 암호화 알고리즘은 기본적으로 외부의 개입이 없습니다. 그러나 세상에는 다양한 프로토콜이 있고, 둘 이상이 통신하며 내용을 주고 받습니다. 이 글에서는 프로토콜의 보안을 어떻게 챙기고 또 암호화폐로 인해 널리 알려진 속성인 영지식성zero-knowledgeness을 다루고자 합니다. 대화형 증명 시스템 NP Revisited Arthur-Merlin Protocol IP 영지식 알리바바와 동굴 Indistinguishability Revisited Fiat-Shamir Protocol Hamiltonian Cycle 마무리 각주 대화형 증명 시스템 대화형 증명 시스템interactive proof system은 두 개체 증명자prover와 검증자verifier로 이루어져...
-
evenharder's profile image
evenharder
November 21, 2020
공개 키 암호화 시스템과 수학적 안전성
이 글에서는 공개 키 암호화 시스템이 발전해나가면서 같이 논의된 수학적 개념을 살펴보고자 합니다. 특히, 암호문으로부터 평문을 알아낼 수 없다는 막연한 속성을 수학적으로 어떻게 표현하는지 알아보고자 합니다. 목차는 다음과 같습니다. 공개 키 암호화 시스템 배경 지식 공개 키 암호화 시스템의 정의 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....
-
evenharder's profile image
evenharder
October 26, 2020
양자 컴퓨팅 - 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 등으로 양자 컴퓨팅 프로그래밍 언어를 사용할 수도 있습니다. 그러나 이런 시스템이 물리적인 양자 체계와...
-
evenharder's profile image
evenharder
August 18, 2020
UCPC 2020 출제 후기
국내에서 가장 불꽃 튀는 알고리즘 대회 중 하나인 UCPC 2020 예선이 지난 7월 25일에, 본선이 8월 1일에 진행되었습니다. 저는 예선의 E번 감자 농장, H번 사과나무 그리고 본선의 G번 그건 망고가 아니라 고양이예요를 출제할 기회를 얻었습니다. 이 포스팅에서는 UCPC에서 문제를 제출한 순간부터 대회가 끝날 때까지 문제 개발이 어떻게 이루어졌는지를 다루어보고자 합니다. 테스트 케이스 제작에 초점을 두지만, 일반적인 검수 과정에 있어서도 길라잡이가 될 수 있으리라 생각합니다. 제가 만든 문제들을 해부하듯이 설명하기 때문에, 풀이도 서술되어 있음에 유의해주시길 바랍니다....
-
evenharder's profile image
evenharder
June 18, 2020
양자 컴퓨팅 입문 (2) - Grover's Algorithm
Grover’s Algorithm은 정렬되지 않은 데이터베이스에 있는 $N$개의 항목 중 특정한 조건을 만족하는 항목을 $O(\sqrt{N})$에 찾는 알고리즘입니다. 고전 컴퓨팅에서 이 문제를 해결하려면, 간단하지만 느리게 갈 수밖에 없습니다. 전수 조사(brute force)가 유일한 해결책입니다. 당연히 시간 복잡도는 $O(N)$이며, 랜덤하게 셔플해서 순서를 바꾼다 해도 마찬가지입니다. 그리고 이보다 더 나은 시간복잡도로 찾을 수는 없습니다. Grover’s Algorithm은 이 시간복잡도를 $O(\sqrt{N})$으로 낮추는데 성공하였고, 이 시간복잡도가 최적이라는 것이 알려져 있습니다. 또다른 유명한 양자 알고리즘인 Shor’s Algorithm과는 달리 알고리즘 자체가 간단하면서도 심도 있기 때문에...
-
evenharder's profile image
evenharder
April 19, 2020
양자 컴퓨팅 입문 (1) - 개요
“양자(quantum)를 이용해서 상태를 저장하는 컴퓨터를 만들면 어떨까?” 이 허무맹랑할 수도 있는 1981년 리처드 파인만에 의해 제기되었습니다. 양자 컴퓨팅은 암호학 쪽에서 1997년 Shor가 다항 시간에 인수분해를 할 수 있는 양자 알고리즘을 발견하면서 각광받기 시작했습니다. 지금까지도 고전 컴퓨팅으로 인수분해를 다항 시간 안에 할 수 없고, 또 RSA 같은 많은 암호체계가 인수분해의 수학적 어려움(infeasibility)을 기반으로 두고 있는데 다항 시간에 인수분해를 할 수 있다는 소식은 획기적인 발전이었습니다. 또 Grover는 정렬되지 않은 $N$개의 항목 중 특정 조건을 만족하는 항목을 $O(\sqrt{N})$에...
-
evenharder's profile image
evenharder
March 19, 2020
JavaScript의 형변환
JavaScript만큼 프로그래머들이 농담 따먹기를 하는 프로그래밍 언어가 PHP 말고 있을까요? JavaScript의 매력이자 악명 높은 점이 타입의 유연성입니다. 변수를 선언할 때 타입을 지정할 필요가 없으며, 서로 타입이 다른 변수들끼리 연산을 해야 할 때 최대한 에러를 내지 않는 방향으로 진행이 됩니다. 이런 규칙을 통해 ![]+-*만 이용해서 0부터 1000까지 만들라는 이런 문제도 있습니다. 하지만 일반적으로 이런 변환 과정은 갸우뚱할 때가 많으며, 프로그래머 개그의 단골 소재이기도 합니다. 이 포스트에서는 형변환(coercion)에 깔려있는 법칙들을 설명하고자 합니다. Alexey Samoshkin님의 이 포스트에서 지대한...
-
evenharder's profile image
evenharder
January 17, 2020
C/C++의 undefined behavior
C나 C++에 있어서 가장 곤혹스러운 요소 중 하나인 undefined behavior는 입문자부터 숙련자에 이르기까지 까다로운 디버깅을 요합니다. 흔히 나오는 코딩 실수인 배열 인덱스 오류도 undefined behavior이며, 온라인 저지 등에서는 최적화 옵션이 켜지면서 전혀 다른 효과가 일어날 수 있습니다. 꼭 C++에만 국한된 이야기는 아니지만, C++ undefined behavior의 주된 요인 중 하나인 signed integer overflow는 2019년에만 1247개의 CVE 취약점을 낳았습니다. 그렇다고 모든 사람이 C/C++ 스펙을 머릿속에 넣어야 하는 것도 아닐 뿐더러 그럴 수도 없습니다. 이 포스트에서는 undefined behavior의...
-
evenharder's profile image
evenharder
December 13, 2019
C++ STL 컨테이너의 메모리 사용량 (2)
지난 포스트 C++ STL 컨테이너의 메모리 사용량 (1)에서는 list, vector, deque의 내부 메모리 사용량을 분석하고, 어떤 식으로 구현되어있는지 추측해보았습니다. 이번 시간에는 priority_queue, set, map, unordered_map을 다루도록 하겠습니다. priority_queue 컨테이너 priority_queue 컨테이너는 다음과 같은 형태로 정의됩니다. template< class T, class Container = std::vector<T>, class Compare = std::less<typename Container::value_type> > class priority_queue; T는 타입, Container는 내부적으로 사용할 컨테이너, Compare는 heap을 구축하는데 사용할 함수를 의미합니다. 기본적으로 priority_queue는 std::vector<T>를 이용하고, std::less를 통해 max heap을 만듭니다. priority_queue는 heapify 등을 통해서...
-
evenharder's profile image
evenharder
November 14, 2019
C++ STL 컨테이너의 메모리 사용량 (1)
C++로 Problem Solving을 하는 사람도, 일반적인 프로그래밍을 하는 사람도 C++의 컨테이너는 매우 유용하게 사용합니다. 대표적인 예시가 동적 배열인 vector, 이진 탐색 트리인 set 등입니다. 이러한 자료구조를 적재적소에 사용하지 않으면 시간/공간 복잡도가 예상을 뛰어넘을 수 있습니다. 대표적인 예시가 “priority_queue가 set보다 빠르다”는 말입니다. 이는 일반적으로 사실이지만, 왜 그럴까요? 이와 관련된 질문에 답하기 위해 C++ 컨테이너가 메모리를 원소별로 얼마나 할당하고 그 이유는 무엇일지 gmem이라는 라이브러리를 통해 파트별로 알아보도록 하겠습니다. gmem 라이브러리 gmem은 동적으로 메모리를 할당할 때마다 로그를 남기고,...
-
evenharder's profile image
evenharder
October 19, 2019
Problem Solving과 생성함수
간혹 조합론 문제를 해결하다가 점화식이 안 나와서 좌절하고 있을 때, 이 문제는 생성함수를 이용하면 기계적으로 만들어낼 수 있다는 충격적인 코멘트를 받아 언젠가 공부해야지 마음먹고 있습니다. 아쉽게도 정규 교육과정에 포함되어있지 않아서인지 problem solving와 관련된 자료가 드물었습니다. 때문에 이 포스트를 작성하시로 하였습니다. 이 포스트는 생성함수는 무엇이고, problem solving에 적용할 수 있는 방법을 다룹니다. 생성함수란? 일반적으로, 어떤 수열 ${a_i} = (a_0, a_1, a_2, \cdots)$에 대하여, \[f(x) = a_0 + a_1x + a_2x^2 + \cdots + a_nx^n + \cdots...
-
evenharder's profile image
evenharder
September 18, 2019
알고리즘 동아리 방학 모의고사 운영
세미나 운영에 대한 회고 알고리즘 동아리 운영에 있어 세미나를 어떻게 진행해야 할지는 정답이 없는 문제입니다. 너무 양이 많으면 기죽는 회원들이 생기지만 너무 적으면 세미나인지도 모호합니다. 난이도를 보아도 너무 어려우면 진입장벽이 생기고 너무 쉬우면 숙련자들에게 큰 의미가 없습니다. 종강이 다가올수록 줄어드는 관심 또한 문제이며, 방학 때는 정말 좋아하는 사람이 아니고서야 별도의 공부를 하지 않는 경우가 많습니다. 제가 회장으로 있는 알고리즘 동아리인 AlKor도 예외는 아니어서, 방학 때 별도의 세미나를 진행하지 않았습니다. 비록 일부 회원들이 ‘숭고한 알고리즘 캠프’에...
-
evenharder's profile image
evenharder
May 16, 2019
그룹 road to grandmaster 둘러보기
어느 ELO 레이팅이 안 그러겠냐만은, grandmaster라는 칭호는 세계적인 실력자에게 주어지는 칭호입니다. 가장 유명하고 세계적인 Competitive Programming(CP) 플랫폼인 Codeforces에서는 레이팅 2400 이상일 경우 grandmaster로 인정받으며, 닉네임이 붉은 색으로 변합니다. 한국 PS계에서는 이들을 ‘레드’라고 부르기도 합니다. 레드가 어느 정도 수치인지 대략적으로 가늠하자면, 2019년 5월 7일 기준으로 최근 6개월간 rated 대회를 친 사람 중 전 세계에 352명밖에 없습니다 (한국에선 16명). 국내 수준급의 프로그래밍 경시 대회의 대략적인 최소 입상 수준이 레이팅 1900-2100 (통칭 ‘퍼플’)이라는 점을 고려하면 단순히 닉네임에서 빛나는...
-
evenharder's profile image
evenharder
April 10, 2019
bash 단축키 뜯어보기
bash같은 쉘은 정말 강력한 기능을 지니고 있고, 이러한 터미널 및 쉘이 *nix 계열의 심장이라 해도 과언이 아닙니다. 유명한 sudo나 rm -rf /, apt-get, git clone, pip install, gcc -O2 -Wall -o test test.c, echo Hello World! 등등 수많은 커맨드들이 오늘도 전 세계에 컴퓨터에서 돌아가고 있습니다. GUI에서 다양한 클릭과 스크롤을 통해서 진행되는 일들이 CLI에서는 한 줄의 명령어로 된다는 점이 매력이라 할 수 있겠습니다. 쉘은 커맨드 측면에서도 다양한 편의성을 제공하지만, 간단한 단축키를 통해서도 수많은 ‘방향키-지우기-다시 쓰기’를 한...
-
evenharder's profile image
evenharder
March 10, 2019
알고 나면 유용한 TeX 팁들
TeX은 Donald Knuth가 만든 조판 언어이며, 수많은 분야에서 논문, 책자, 강의 자료 등을 만드는 데 사용됩니다. TeX에 대한 찬양을 하기에는 여백이 너무 부족하므로 생략하도록 하겠습니다. 이 포스트는 TeX 설치법이나 입문 또한 다루지 않습니다. 해당 내용은 Overleaf 같은 온라인 TeX 편집기 사이트에서 찾아보시길 바랍니다. 대신, 이 포스트는 어느 정도 TeX을 쓸 수 있는 분들에게 유용할 (혹은 이미 알고 있을) 팁을 다룹니다. 그림 폴더 경로 설정 일반적으로 TeX에 이미지를 넣을 때는 \includegraphics를 사용합니다 (graphicx 패키지 필요). 이...
-
evenharder's profile image
evenharder
February 10, 2019
Hello, Regex!
정규 표현식이란? 정규 표현식(Regular Expression, Regex)는 일정한 규칙을 가진 문자열의 집합을 표현하는데 사용합니다. 정규 표현식은 문자열의 검색과 치환을 위해 종종 쓰입니다. 프로그래밍 코드나 그 산출물에서 규칙이 드러나는 문자열은 무궁무진합니다. 날짜, 도메인 주소 형식, 이메일 형식, 수많은 유틸리티의 출력 형식이 대표적인 예이며, 그 외에도 두 글자 이상의 공백 등 규칙이 있는 문자열을 처리해야 할 때가 있습니다. 정규 표현식을 이용하면 이들을 보다 편하게 탐색하고 감지할 수 있습니다. 정규 표현식은 특히 Perl에서 그 확장성이 뛰어나며, 그외 수많은 언어들과...
-
evenharder's profile image
evenharder
January 10, 2019
2018 고려대학교 프로그래밍 경진대회 (KCPC) 출제 후기
이 포스트는 2018년 고려대학교 프로그래밍 경진대회 출제 과정에 있었던 일들과 대회의 지향점 및 결과 및 사견을 다룹니다. 원래 대회가 끝나고 바로 쓰고 싶었으나 대회 1주일 후가 기말고사이기도 했고 준비가 워낙에 힘들었기 때문에 한 달이 지난 지금 쓰게 되었습니다. 우선 본 대회를 성공적으로 마무리해주신 운영진과 출제진에게 감사하다는 말을 드리고 싶습니다. 또, 본 대회의 규모 확장에 필수불가결한 기여를 해주신 Startlink, sooho, wishket, NAVER D2, vcnc, 삼성 소프트웨어 멤버십, 고려대학교 정보대학 SW중심대학, 정보보호학부 및 정보보호대학원과 관계자 분들께 감사의...