-
Block Decomposition을 이용한 Online FFT 구현
Introduction 이 글에서는 Block Decomposition을 이용한 Online FFT(Fast Fourier Transform) 구현 방법을 소개합니다. 두 수열 $A$, $B$의 convolution $C$를 $\mathcal{O}(n\log n)$에 구하는 FFT 알고리즘은 두 수열 $A$, $B$가 모두 주어져야만 사용할 수 있습니다. Online FFT는 $A$, $B$의 원소 $a_i$, $b_i$가 하나씩 주어질 때 $c_i$를 온라인으로 구하는 알고리즘입니다. 이는 점화식이 convolution 형태이면서 $c_0, \cdots, c_{i-1}$을 알아야 $a_i$, $b_i$를 구할 수 있는 경우(예를 들면 카탈란 수 $C_{n+1} = \sum_{i=0}^n C_i C_{n-i}$)에 사용할 수 있습니다. Online FFT는 여러...
-
Custom Select Box 만들기 (overflow 문제 해결) - (Nuxt3, Vue3)
Intro 안녕하세요. 이번 글에서는 Nuxt3에서 Custom Select Box를 구현해보려고 합니다. 이때, overflow를 허용하는 Component 내부에 존재하는 Custom Select Box에 대해 생기는 스크롤 문제를 해결하는 것이 이 글의 목표입니다. 명확한 해결책을 제시해 주는 곳이 없어 이를 해결할 수 있는 방법을 공유하고자 합니다. 또한, Select Box 외에도 Tooltip과 같이 특정 컴포넌트가 position: absolute인 상태로 상대 위치를 계산해야 하는 상황에서도 동일한 방법으로 해결할 수 있습니다. Nuxt3로 작성된 글이긴 하지만, javascript 기반으로 작동하는 여러 트릭이 많아서 굳이 Nuxt3를 몰라도,...
-
LCS 알고리즘 최적화
개요 LCS(Longest Common Subsequence) 문제는 두 문자열의 공통 부분 수열 중 가장 긴 것을 찾는 문제로, 컴퓨터과학에서 가장 고전적이면서 중요한 문제 중 하나입니다. 이 글에서는 이 문제를 해결하는 간단한 Dynamic Programming 해법부터, 이것의 공간 복잡도를 개선한 Hirschberg 알고리즘과, 일반적인 문자열에서 더 효율적인 Hunt-Szymanski 알고리즘을 소개할 것입니다. 그리고 이들을 비트 집합을 이용해 더욱 최적화하는 방법을 다룰 것입니다. 간단한 DP 해법 $DP[i][j]$를 $A$의 길이 $i$인 접두사와 $B$의 길이 $j$인 접두사의 LCS 길이로 정의하면 다음과 같은 점화식으로 $A$와...
-
GSW : Homomorphic Encryption with Gadget
Introduction 안녕하세요. 이전 글에서는 TFHE라는 동형암호를 다루기 위한 기본적인 암호화, 복호화와 덧셈 연산이 어떻게 이루어지는지를 알아보았습니다. 이번 글에서 다루는 주제는 동형암호는 맞으나 TFHE는 아닌데요. 이는 TFHE scheme 중간에 등장하게 되는 개념인 GGSW sample이라는 개념이 바로 지금 제가 다루고자 하는 동형암호인 GSW scheme[1] 에서 가져온 것이기 때문에, 중간에 한 번 쉬어가더라도 GSW scheme과 gadget이라는 개념을 다루고 가는 것이 도움이 될 것이라 생각해서 GSW scheme에 대한 글을 먼저 쓰게 되었습니다. 동형암호의 개념 자체에 대해 생소하신 분이라면 먼저...
-
Gröbner Basis와 Buchberger's algorithm, 그 활용
목표 Gröbner Basis는 주어진 몇 개의 다항식들로 생성되는 환에 대한 분석을 쉽게 해주는 강력한 툴입니다. 이 포스트의 목표는 Gröbner Basis를 구할 수 있는 Buchberger’s algorithm과 그 정당성에 대해 직관적으로 이해하고, Gröbner Basis를 통해서 해결할 수 있는 문제들에 대해 알아보는 것입니다. 사전지식 - Basic Algebra 이 단락에서는 환과 아이디얼이 무엇인지에 대해 다룹니다. 환이라는 것은, 간단히 말해 덧셈과 곱셈이 정의되어있고, 결합법칙, 분배법칙, 덧셈에 대한 교환법칙이 성립하며, 덧셈에 대한 항등원과 역원이 존재하고, 곱셈에 대한 항등원이 존재하는 대수구조를 말합니다....