-
Linear-Time Encodable Linear Code
Error-correcting code $[n, k, d]$ code: 길이 $k$인 message $m$을 길이 $n$인 codeword $Enc(m)$으로 인코딩하는 $Enc$에 대해, 서로 다른 두 message의 codeword의 hamming distance (서로 다른 entry의 개수)가 항상 $d$ 이상일 때 이를 $[n, k,d]$ code라 합니다. 이 때 가장 가까운 두 codeword가 서로 다른 비율을 나타내는 $\Delta = \frac{d}{n}$을 code의 relative distance라고 부릅니다. Example: Repitition code 예를 들어, “0101”을 “000111000111”로 encoding하는, 원래의 비트를 세 번씩 반복하는 repitition code의 경우 이는 $[3k, k, 3]$ 코드이고,...
-
sweepline MO
개요 다음 문제를 생각해 봅시다. Static Range Inversions Query 길이가 $N$인 수열 $A = (A_1, A_2, \dots, A_{N})$가 주어지면, 다음 $Q$개의 쿼리를 수행해야 합니다. $(1 \leq N \leq 10^5, 1 \leq Q \leq 10^5, 0 \leq A_i \leq 10^9)$ $1 \leq l \leq r \leq N$을 만족하는 $l,r$이 주어지면, $l \leq i < j \leq r, A_i > A_j$ 를 만족하는 $(i,j)$쌍(=inversion)의 개수를 출력한다. 이 글에서는 다음의 내용들을 다룰 것입니다. Static Range Inversions Query 문제를...
-
Multi-Armed Bandit and UCB Algorithm
소개 이 글에서는 불확실성 속에서 좋은 선택을 찾아내야 하는 문제인 Multi-Armed Bandit 문제가 무엇인지 소개하고, 이를 해결하는 알고리즘 중 하나인 UCB 알고리즘을 최대한 쉽고 직관적인 방식으로 유도하고 증명할 것입니다. 기초적인 확률론과 통계학 (ex. 확률분포, 기댓값, 모평균 표본평균)에 대한 지식이 필요하지만 그 외의 배경지식이 없는 사람도 이해할 수 있게 작성했습니다. 문제 설명 돈을 주는 기계? 당신 앞에 2개의 버튼이 달린 기계가 있습니다. 놀랍게도, 이 기계는 버튼을 누르면 돈이 나옵니다! 그리고 운 좋은 당신은 어느 쪽이든 버튼을...
-
BFV scheme에 대한 소개 - 4
Introduction 지금까지 BFV Scheme에 관한 설명글들을 썼고, 저번 글에서는 RNS form에서 처리하기 까다로운 연산 중에서 BFV decryption을 어떻게 처리하는지에 대해서 설명했습니다. 이번 글에서는 multiplication을 어떻게 처리하는지에 대해서 설명하도록 하겠습니다. Backgrounds 이번에 설명할 연산은 RNS module의 BFV scheme에서 multiplication 입니다. 얼핏 생각했을 때, decryption에서 rounding을 correction하는 법도 이미 구했고, Multiplication 역시 비슷하게 하면 되지 않을까? 라는 생각을 할 수 있습니다. NTT등을 사용하면 속도도 빠르게 나올 것입니다. 하지만, 그냥 곱하는 방법을 쓰면 문제가 있는데, 바로 Noise Growth가...
-
알고리즘 문제 접근 과정 12
알고리즘 문제 접근 과정 12 이번 포스트에서도 ‘알고리즘 문제 접근 방법’ 시리즈에서 진행했듯이 특정 문제를 해결하기 위해 가장 낮은 단계의 접근에서부터 최종 해법까지 해결해나가는 과정을 작성합니다. 다만 기존과는 조금 달리, 이번에는 JOI 기출문제들 중 높은 난이도의 문제들을 위주로 이야기합니다. JOI 기출문제들은 좋은 문제들이 많음에도, 한글로 번역이 되어있지 않고 한글 풀이가 존재하지 않는 문제들이 있어, 이들 위주로 풀이를 작성하려고 합니다. 이번 문제들의 난이도는 기존 시리즈들과는 달리, 기출문제들 중 높은 번호의 문제들을 다루다보니 조금 어렵게 느껴질 수...