-
Object Detection
Object Detection Computer Vision(컴퓨터 비전)이란 컴퓨터 공학의 관점에서, 인간의 시각 시스템이 할 수 있는 작업을 구현하고 이를 자동화하는 방법을 다루는 학문입니다. 이를 위해 이미지 및 비디오에 대한 수집, 처리, 분석을 진행하기 위해 필요한 여러가지 주제들에 대한 연구가 이루어지고 있습니다. Object Detection(객체 감지)란 컴퓨터 비전의 하위 분야 중 하나로 전체 디지털 이미지 및 비디오 내에서 유의미한 특정 객체를 감지하는 작업을 합니다. 이러한 object detection은 Image retrieval(이미지 검색), Image annotation(이미지 주석), Face detection(얼굴 인식), Video Tracking(비디오 추적)...
-
Improved Non-Interactive Zero Knowledge with Applications to Post-Quantum Signatures
1. Introduction 저번 글에서는 MPC를 이용한 Zero-Knowledge Proof에 대해 다루었습니다. 쉽게 요약을 해보자면 MPC-in-the-head를 이용해 증명자는 SHA256(x) = y를 만족하는 y를 알고 있다는 사실을 x를 공개하지 않고 검증자에게 납득시킬 수 있습니다. 더 나아가 원래의 증명은 검증자의 질의에 대해 증명자가 대답하는 방식으로 진행되나 Fiat-Shamir Transform을 사용하면 Non-Interactive로 증명을 만들 수 있습니다. 이렇게 Ishai et al.이 MPC-in-the-head를 제안한 후 Giacomelli et al.은 실제로 MPC를 수행하는 ZKBoo 프로토콜을 만들어냈습니다. 한편, Zero-Knowledge Proof로부터 전자서명을 만들 수 있습니다. 이건 사실...
-
대회/코딩 테스트용 간이 테스터 만들기
개요 프로그래밍 문제를 풀다 보면 종종 맞왜틀 (맞았는데 왜 틀려요)의 벽에 부딪히게 됩니다. 예제도 다 맞고, 열심히 생각해서 넣어본 여러 케이스들도 맞는데도 제출만 하면 틀렸다고 하고… 도무지 반례가 안 보일 때의 답답함은 말로 표현할 수가 없습니다. 연습용으로 문제를 풀 때에는 그나마 Polygon과 같은 전문 도구를 사용해서 스트레스를 돌리거나 견고하게 짜여진 테스트용 도구를 로컬에서 실행해보면서 반례를 찾을 수도 있습니다. Polygon의 사용법은 Acka1357 님의 글 문제 출제를 위한 플랫폼 - Polygon 사용하기에서 자세하게 확인할 수 있습니다. 하지만...
-
Factor Base를 이용한 "어려운 문제"의 속도 개선
이 글에서는 factor base를 활용한 속도 개선을 언제 사용할 수 있는지, 사용할 경우 시간 복잡도의 개선이 정확히 얼마나 일어나는지, 실제로는 얼마나 빠른지를 알아봅니다. “어려운 문제”? 이 글에서의 어려운 문제는 크게 소인수분해와 이산 로그를 일컫습니다. 소인수분해 문제는 잘 알고 계실 것입니다. 수 $N$이 주어지면, $N$을 (서로 다를 필요는 없는) 소수 $p_{1}$, $p_{2}$, $\cdots$, $p_{n}$의 곱 $N = p_{1} p_{2} \cdots p_{n}$으로 분해하라. 예를 들어 $108 = 2 \cdot 2 \cdot 3 \cdot 3 \cdot 3 =...
-
스킵 리스트
서론 다음 연산을 모두 $O(logn)$에 지원하는 자료구조가 필요합니다. x를 추가한다. x를 삭제한다. x 이상의 원소 중 가장 작은 것을 출력한다. C++에서는 std::set가 바로 이 역할을 하지만, Python에는 이런 내장 라이브러리가 없습니다. 그래서 외부 라이브러리를 쓰지 않는 한 레드-블랙 트리나 AVL 트리 등을 직접 구현해야 하는데, 트리 자료구조는 보통 rebalancing 과정이 복잡합니다. 한편, 트리의 틀을 벗어나면 스킵 리스트 (Skip List)라는 자료구조가 있습니다. “평균”이라는 말에서 추측할 수 있듯이, 랜덤을 사용한다는 특징이 있습니다. AVL 트리 등에 비해 구현이...