-
USACO 활용하여 문제 풀어보기
서론 USACO란 미국의 정보올림피아드로, 어렵지 않은 알고리즘을 이용하여 문제를 출제됩니다. 학생들은 등급별로 3개의 문제를 풀며 Bronze부터 Platinum 까지 승급하며 올라가는 방식입니다. 이번에는 2021년 12월에 진행되었던 USACO Silver, Gold 시험의 1번문제의 풀이를 하려 합니다. Closest Cow Wins (USACO Silver #1) 이 문제는 $K$개의 풀밭이 각각 $p_i$ 위치에 $t_i$의 맛을 가지고 있습니다. Nhoj와 John은 소를 배치하는데, 각 풀밭은 가까이에 있는 소에게 먹히게 됩니다. Nhoj의 소와 John의 소가 풀밭에서 같은 거리에 있을 때에는, Nhoj의 소가 먼저 먹게 됩니다....
-
Reverse Engineering of Generative Models
Introduction 이번 글에서는 페이스북 AI Research가 작성한 Reverse Engineering of Generative Models: Inferring Model Hyperparameters from Generated Images 논문을 소개하고자 합니다. 이 논문은 최근 딥러닝 기술의 발달로 딥페이크가 악용되고 있는 상황에서, 딥페이크를 추적하는 기술이 어떤 것이 있나 조사하는 과정에서 알게 되었습니다. 본 논문은 딥페이크 판별과 더불어 딥페이크 이미지를 생성한 모델의 property까지 추론한다는 점에서 다른 딥페이크 탐지 기술과 차별화됩니다. 또한 AI 모델의 연구 진행 과정이 잘 보이는 것 같아서 소개하게 되었습니다. 작성된 내용은 논문과 저자들 중...
-
Zero Knowledge and Groth16 Protocol
서론 최근 회사에서 Groth16, Powers of Tau, Tornado Cash에 대한 세미나를 진행했습니다. 이번 글에서는 해당 세미나의 첫 주제인 Groth16에 대해서 정리하는 시간을 갖겠습니다. 세미나 발표자료는 https://github.com/rkm0959/rkm0959_presents/blob/main/TornadoCash.pdf 에서 확인하실 수 있습니다. Zero Knowledge Proof (ZKP) Zero Knowledge Proof란, 비밀키의 소유를 증명하고자 하는 사람이 자신의 소유 사실에 대한 증명을 하되, 이를 넘어선 다른 정보는 아예 공개되지 않도록 하는 방법론입니다. 예를 들어서, Discrete Logarithm 문제가 있다고 합시다. $G$는 $\lvert G \rvert =q$가 소수인 generic group이고, $g, h$가 $G$의...
-
Minimum Steiner Tree의 계산
서론 그래프 $G$와, 정점의 부분집합 $T$가 주어졌을 때, $T$를 모두 포함하는 Spanning Tree ($G$의 부분그래프 중, 정점과 간선 일부를 선택하여 만든 트리)를 $T$의 Steiner Tree라고 한다. 가중치가 주어진 방향 없는 그래프 $G$에 대해 간선 가중치 합이 가장 작은 Steiner Tree를 계산하는 문제는 일반적인 상황에서 NP-Hard임이 알려져있다. 이 게시글에서는, 해당 Steiner Tree를 계산하는 동적계획법을 다룬다. Naïve 편의상, 그래프의 $G = (V, E)$의 정점 개수를 $N$, 간선 개수를 $M$, 정점 부분집합 $T$의 크기를 $K$라고 하자. 가장 쉽게...
-
Stern-Brocot Tree를 활용한 수론적 함수의 합 계산
개요 정수론에서 주로 다루는 중요한 수론적 함수로는 약수 함수 $\sigma_k (n)$, 오일러 피 함수 $\phi (n)$, 뫼비우스 함수 $\mu (n)$ 등이 있다. 이러한 함수의 학문적 중요도는 이루 말할 수 없으며, 컴퓨터과학와 PS 분야에도 종종 등장할 정도로 다양하게 활용된다. 본 글은 수론적 함수의 대표인 약수 함수 $\sigma (n)$의 구간 합을 효율적으로 계산하는 알고리즘을 서술한다. 함수의 합을 기하적으로 해석한 후, 이를 Stern-Brocot Tree 자료구조로 계산한다. 이후, 이 알고리즘의 시간 복잡도가 $\tilde{O} \left( N^{1/3} \right)$로 아주 효율적임을 보인다....