-
Segment Tree Beats와 Kinetic Segment Tree
Segment Tree Beats와 Kinetic Segment Tree 이 글에서는 Kinetic Segment Tree라는 새로운 세그먼트 트리를 소개한다. 어떠한 원소가 Kinetic하다는 것은 시간에 따라서 움직인다는 것으로, 쉽게 말해 그 원소가 일차함수거나 다항함수라는 것이다. 세그먼트 트리도 대회에 자주 나오고, Kinetic한 원소도 대회에 자주 나오니 (대표적으로 컨벡스 헐 트릭), 그것의 조합 역시 익혀보면 도움이 될 것이다. 또한, Kinetic한 원소와 전혀 상관이 없는 문제들에서도 Kinetic한 성질이 파악된다는 점에서 착안하여 (대표적으로 CHT를 사용한 DP 최적화), 이 Kinetic Segment Tree가 어떻게 응용될 수...
-
ICPC World Finals 2021 풀이
11월에 ICPC World Finals 2021에 참가했습니다. 이후 11월 말까지 한 문제를 제외한 나머지를 모두 풀었고, 이 글에서 모든 문제의 풀이를 정리합니다. 최근 3년과 달리 상대적으로 쉬운 (플래티넘 하급 이하) 문제가 좀 더 많이 나왔는데, 그것들을 푸느라 더 어려운 문제에 쓸 시간이 부족했습니다. A: Crystal Crosswind 바람의 방향이 $(w_x, w_y)$, 가장자리의 집합이 $S$라고 하면 다음과 같은 정보를 얻습니다. (1) $(x, y) \in S$일 경우, $(x, y)$은 분자고, $(x - w_x, y - w_y)$는 빈칸입니다. (2) $(x,...
-
Local Differential Privacy
들어가며 지난번에는 어느 한 데이터셋에서 하나의 데이터가 가지는 영향력에 대해서 공부해 보았습니다. 어떤 데이터셋에서 한 데이터를 제외한 나머지 정보를 다 알고 있을 때, 나머지 한 개의 데이터를 유출할 수 있는지에 대한 것이었습니다. Differential Privacy는 이를 수식을 활용해 표현한 것으로, $\epsilon$의 값으로 데이터의 안정성을 확인할 수 있었습니다. 이번에는 Differential Privacy와는 조금 다르지만 개인의 프라이버시를 보호할 수 있는 개념을 소개하려고 합니다. 개인이 신뢰하지 않는 서버에 데이터를 제공했을 때의 프라이버시를 보호하기 위한 개념인 Local Differential Privacy에 대해 소개하려고...
-
Homomorphic Encryption에 대한 소개
Introduction 올 한해 크립토랩이라는 스타트업에서 근무할 기회가 있었습니다. 크립토랩은 Homomorphic Encryption, 즉 동형암호 scheme 중 CKKS를 바탕으로 창업한 스타트업입니다. (CKKS scheme을 제안하신 천정희 교수님이 대표입니다.) 회사에서 근무하며 그동안 잘 몰랐던 동형암호에 대해서 배울 기회가 있었습니다. 현재 국내에는 동형암호에 대해 서술하는 자료가 그리 많지 않은 것으로 보여, 동형암호에 대한 소개글을 작성하기로 했습니다. What is Homomophic Encryption? 먼저 동형암호가 무엇인지 간단하게 설명하도록 하겠습니다. 우선 보통의 암호 scheme의 경우 평문(plaintext)와 암호문(ciphertext)의 관계를 최대한 random하게 만드려고 합니다. 평문과 암호문...
-
RandomMix: A mixed sample data augmentation method with multiple mixed modes
RandomMix: A mixed sample data augmentation method with multiple mixed modes RandomMix는 2022년도 5월 난징대에서 연구하여 arxiv에 공개된 data augmentation 논문입니다. 꽤나 최근에 나온 논문으로, 논문 자체의 내용이 크게 어렵지 않으면서도 지금까지 발표된 여러가지 mixed sample data augmentation들에 비해 높은 성능을 보여 SOTA를 달성했습니다. 뿐만 아니라 이미지의 robustness, diversity, cost의 관점에서도 좋은 향상을 보여주어 살펴볼 필요가 있는 논문입니다. 들어가기에 앞서, 본 글은 해당 논문을 그대로 번역하는 것이 아닌 관련된 다른 논문들의 설명을 추가하며 RandomMix 및...