-
Gröbner Basis와 Buchberger's algorithm, 그 활용
목표 Gröbner Basis는 주어진 몇 개의 다항식들로 생성되는 환에 대한 분석을 쉽게 해주는 강력한 툴입니다. 이 포스트의 목표는 Gröbner Basis를 구할 수 있는 Buchberger’s algorithm과 그 정당성에 대해 직관적으로 이해하고, Gröbner Basis를 통해서 해결할 수 있는 문제들에 대해 알아보는 것입니다. 사전지식 - Basic Algebra 이 단락에서는 환과 아이디얼이 무엇인지에 대해 다룹니다. 환이라는 것은, 간단히 말해 덧셈과 곱셈이 정의되어있고, 결합법칙, 분배법칙, 덧셈에 대한 교환법칙이 성립하며, 덧셈에 대한 항등원과 역원이 존재하고, 곱셈에 대한 항등원이 존재하는 대수구조를 말합니다....
-
TFHE : Fully Homomorphic Encryption over the Torus - 1
Introduction 동형암호, 영어로는 HE(Homormorphic Encryption), 또는 FHE(Fully Homomorphic Encryption)은 일반적인 암호와 다르게, 암호화된 상태에서도 연산이 가능하게 하는 scheme입니다. 예를 들어, 어떤 기업에서 MRI 결과를 입력으로 받아 그 MRI를 찍은 사람이 암에 걸렸을 확률을 계산하는 알고리즘을 개발했다고 합니다. 원래는 그 기업에게 자신의 MRI를 공개해야만 그 결과를 받아볼 수 있었을텐데, 동형암호와 함께라면 자신의 MRI를 암호화해서 보낸 뒤, 암호화된 MRI 결과를 기업이 연산하고, 받은 결과를 복호화하면 기업은 아무런 내용도 알 수 없는 것입니다! 더 자세한 개념이 궁금하시다면 이...
-
solving JIE-constant (acmicpc 22222)
문제 소개 지애 상수는 백준의 22222번째 문제를 기념하여 출제된 문제로, 문제에서 정의된 지애 상수라는 값을 소수점 222자리까지 구하는 문제입니다. 지애 상수의 정의는 아래와 같습니다. Definition of 지애 상수 지애 상수는 좌표평면의 점 $A(0,0),B(1,0),C( {1 \over 2} , { \sqrt 3 \over 2})$로 정의된 정삼각형 $ABC$에서 시작하여 만든 시에르핀스키 삼각형에서 독립적으로 균등하게 잡은 점 두 개의 유클리디안 거리의 기댓값입니다. 균등하게 점 잡기? 지애 상수를 정의하기 위해서는 우선 시에르핀스키 삼각형에서 점을 균등하게 잡는 것을 수학적으로 정의할 수...
-
Mukjjippa (BOJ 32469)
이 글은 2024 KAIST 14th ICPC Mock Competition에 출제했던 문제 중 하나인 Mukjjippa (BOJ 32469)에 대해 다룬다. Problem 두 플레이어 A와 B가 묵찌빠라는 게임을 한다. 이 게임은 여러 턴으로 이루어진다. $i$번째 턴($1\le i\le n$)에서: 각 플레이어는 $\{\mathrm R,\mathrm S,\mathrm P\}$에서 정확히 하나를 선택한다. (각각 묵(rock), 찌(scissors), 빠(paper)를 나타낸다.) $X_i$와 $Y_i$를 각각 A와 B의 선택이라 하자. 만약 $(X_i, Y_i) \in \{(\mathrm R,\mathrm S),(\mathrm S,\mathrm P),(\mathrm P,\mathrm R)\}$라면, A가 $(i+1)$번째 턴의 공격자가 되고 게임은 계속된다. 만약 그렇지...
-
다양한 그래프 표현 방법
개요 그래프는 다양한 방법으로 표현될 수 있습니다. 각 방법은 특정 상황에서 장단점을 가지며, 문제의 요구 사항에 따라 적절한 표현 방법을 선택하는 것이 중요합니다. 이 글에서는 그래프를 표현하는 4가지 방법인 인접 행렬(Adjacency Matrix), 인접 리스트(Adjacency List), CSR(Compressed Sparse Row), 그리고 XOR Linked Tree에 대해 설명합니다. (XOR Linked Tree 개념은 코드포스 글 https://codeforces.com/blog/entry/135239을 참고해 작성했습니다) 1. 인접 행렬 (Adjacency Matrix) 개념 인접 행렬은 그래프를 2차원 배열로 표현하는 방법입니다. 그래프에 i번 정점에서 j번 정점으로 가는 간선이 있다면 i행...