-
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 기출문제들은 좋은 문제들이 많음에도, 한글로 번역이 되어있지 않고 한글 풀이가 존재하지 않는 문제들이 있어, 이들 위주로 풀이를 작성하려고 합니다. 이번 문제들의 난이도는 기존 시리즈들과는 달리, 기출문제들 중 높은 번호의 문제들을 다루다보니 조금 어렵게 느껴질 수...
-
Randomized Algorithm의 시간 복잡도 분석
Introduction 우리가 PS에 대해 배우면서 학습하는 대부분의 알고리즘은, 확률에 의존하지 않는다. 해당 알고리즘의 로직을 올바르게 구현했을 때에는 항상 정해진 시간 복잡도로 정답을 낸다. 현대 연구되는 많은 알고리즘은 그렇지 않다. 알고리즘은 확률적으로 오답을 낼 수도 있고, 정답과 적절히 가까운 근삿값만을 계산할 수도 있다. 또는 알고리즘의 수행 시간이 확률적으로 들쑥날쑥할 수 있다. 이러한 알고리즘의 가장 간단한 예시로는 피벗을 무작위로 잡는 퀵 소트 알고리즘이 있다. 무작위 알고리즘 (Randomized algorithm) 가운데, 항상 정답을 내는 것이 보장된 알고리즘을 Las Vegas...
-
Piece Table
서론 텍스트 에디터는 하나의 문자열을 조작하는 것을 매우 빠르게 하는 자료구조가 필요합니다. 길이가 $n$인 문자열 $s$에 대해서 다음과 같은 기능들이 있어야 합니다: $s = s[0..i] + s[j..n], 0 \le i < j \le n$, 즉, $i$ ~ $j$까지의 문자들을 지운다 $s = s[0..i] + t + s[i..n]$, 즉, $i$ 위치에 문자열 t를 넣는다 $s[i..j]$, 즉, $i$부터 $j$까지의 문자열을 빠르게 구한다 텍스트 에디터에는 문자열 찾기, 줄 번호 등 여러 기능이 있어야 하지만 우선 가장 중요한 기능은...