-
Differential Privacy
들어가며 IT기술들이 발전하며 개개인의 데이터 가치는 나날이 높아지고, 그만큼 관심이 많아지고 있습니다. 얼마 전에는 구글과 메타가 개인정보 불법수집으로 인해 과징금을 내는 등, 회사들에서도 개인정보에 관심을 가지고 있습니다. 개인정보들 중에서도 조금더 민감한 정보들이 있을 수 있습니다. 이름이나 생일같은 정보는 하나만 있으면 개인을 특정하기 굉장히 어렵지만, 희귀병이 있다거나 하는 등 한 가지의 정보만 있더라고 개인을 특정할 수 있는 문제들도 있습니다. 이번에는 이러한 데이터들을 어떻게 privacy를 지키면서 관리할 수 있는지에 대해 알아보려고 합니다. Differential privacy 이전부터는 Database에 데이터를...
-
알고리즘 문제 접근 과정 11
알고리즘 문제 접근 과정 11 이번 포스트에서도 ‘알고리즘 문제 접근 방법’ 시리즈에서 진행했듯이 특정 문제를 해결하기 위해 가장 낮은 단계의 접근에서부터 최종 해법까지 해결해나가는 과정을 작성합니다. 최대한 다양한 유형의 문제들을 다루어, 많은 문제 유형에서의 접근 방법에 대한 실마리를 드리는 역할을 하려 합니다. Two Machines - ICPC 2019 Seoul Nationalwide Internet Competition L번 관찰 주어진 문제를 간단히 본다면, 머신 A와 머신 B에서 각각 작업에 걸리는 시간이 다른 N개의 일을, A와 B에 적절히 할당하여 동시에 일을 진행하고,...
-
도형의 합집합과 넓이
도형의 불리언 연산이란, 여러 도형의 영역에 대한 집합 연산을 말합니다. 두 원의 교집합의 넓이를 구하는 방법은 잘 알려져 있습니다. 부채꼴 2개의 넓이를 합친 다음, 이등변삼각형 2개의 넓이를 빼는 방식으로 구할 수 있습니다. 같은 방법으로 두 원의 합집합의 넓이도 구할 수 있습니다. 하지만 원이 3개만 되어도 이런 “포함 배제” 접근을 하기 어렵습니다. 이 글에서는 도형의 합집합 및 그 넓이를 구하는 일반적인 방법을 소개합니다. 테두리 따기 아래 그림에서 테두리가 갖고 있는 중요한 성질을 찾아봅시다. 테두리는 도형의 둘레로...
-
Kirchhoff's Theorem (Matrix-Tree Theorem)
이번 글에서는 그래프의 스패닝 트리의 개수를 세는 두 가지 정리, Cayley’s formula와 Kirchhoff’s theorem에 대해 소개합니다. Cayley’s Formula 일반 그래프의 스패닝 트리의 개수를 세어보기에 앞서, 특수한 경우부터 먼저 살펴봅시다. Theorem 1 (Cayley’s Formula). $n$개의 정점으로 이루어진 완전그래프 $K_n$의 스패닝 트리의 개수는 $n^{n-2}$이다. 이 정리를 증명하는 방법으로는 여러 가지가 알려져 있으며, 대표적으로 Prüfer sequence와의 일대일 대응 관계를 찾는 증명이 있습니다. 개인적으로 가장 마음에 드는 증명은 다음과 같은 더블 카운팅을 이용한 증명입니다. 책 “하늘책의 증명” (Proofs from...
-
Low degree optimal polynomial의 계산기하적 접근
Optimal Polynomial 일반적으로 함수 $f(x)$와 차수 $d$가 주어졌을 때, $\lvert P(x) - f(x) \rvert$의 최댓값 를 최소화하는 $d$차 다항함수를 $f$에 대한 degree $d$의 optimal polynomial 이라 합니다. 그러나 이러한 $P$를 구해야 하는 상황에서는 보통 함수 $f$를 모르는 상태에서, $f$가 $d$차 이하의 다항식일 것이라고 가정한 후 $P$를 추측해야 하는 경우가 잦습니다. 몇 개의 $x_i$에 대해 $f$의 실험값 $y_i = f(x_i) + \epsilon_i$ 가 주어져있을 때 오차 $\max (\lvert P(x_i) - y_i \rvert)$를 최소화하는 $P$를 어떻게 구할...