-
Solving 8-puzzle problem with search algorithm
Abstract 8-퍼즐 문제는 3X3 크기의 프레임과 1부터 8까지의 숫자로 이루어진 슬라이딩 퍼즐을 순서대로 배열하는 문제입니다. 더 일반화된 문제는 N-퍼즐 문제로, 최적의 해를 찾는 것이 NP-hard라고 합니다. 이번 글에서는 가장 기본적인 BFS, DFS에서부터 IDS 알고리즘, A* 알고리즘까지의 방법론으로 8-퍼즐 문제를 풀어보고, 그 성능을 분석해보도록 하겠습니다. 8-퍼즐 문제 8-퍼즐은 3X3 그리드로 나누어진 정사각형 프레임 안에 8개의 타일과 하나의 빈 공간이 있는 슬라이딩 타일 퍼즐입니다. 아마 한번쯤은 해보셨을 것으로 생각됩니다. 8-퍼즐 각 타일은 서로 구분되는데, 보통은 1부터 8까지의...
-
Optimal Ate Pairings, BLS12-381, BN254 알아보기
이전 글에서 이어서 가겠습니다. Optimal Ate Pairings [Ver09]의 내용입니다. 다시 Tate Pairing으로 돌아가서, \[(f_{s, P}) = s(P) - ([s]P) - (s-1) \mathcal{O}\] 인 함수 $f_{s, P}$를 생각하면, reduced Tate Pairing \[t_r(P, Q) = f_{r, P}(Q)^{(q^k - 1) / r}\] 를 얻을 수 있었습니다. 이제 이를 최적화하는 Ate Pairing을 알아봅시다. Lemma \[f_{ab, Q} = f_{a, Q}^b \cdot f_{b, [a]Q}\] 증명: 단순 계산. 어렵지 않습니다. 그러면 특히 $[r]Q = \mathcal{O}$인 경우에는 \[f_{mr, Q} = f_{r, Q}^m\] 가...
-
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에 대해 소개하려고...