-
Variation of Mo's Algorithm 1
안녕하세요 jthis 입니다. 이 글에서는 Mo’s Algorithm의 variation에 대해 소개하겠습니다. Mo’s Algorithm Mo’s Algorithm은 구간 쿼리를 offline으로 해결하는 알고리즘입니다. Mo’s Algorithm에 대한 자세한 설명은 Mo’s Algoithm에서, Mo’s Algorithm을 사용한 트리의 서브 트리에 대한 쿼리나 경로에 대한 쿼리는 Mo’s on Tree 에서 찾아보실 수 있으니 읽고 오시면 도움이 될 것입니다. Mo’s Algorithm with Rollback Mo’s Algorithm을 사용할 때 원소를 제거만 하거나 삽입만 하고 싶다는 생각을 해보신 적 있으실 겁니다. 간략하게 설명하자면 원소를 삽입하는 연산만 하고 싶을...
-
다양한 언어에서의 async/await
동시성과 병렬성, 멀티쓰레드와 멀티프로세스 무어의 법칙이란 반도체 성능이 24개월마다 2배씩 증가하게 된다는 법칙입니다. 이 법칙은 최근까지 잘 맞아떨어지지만 이제는 한계에 가까워졌다고 합니다. 그래서 최근에는 CPU의 코어 수를 늘리는 추세입니다. 즉, 프로그래머는 CPU의 많은 코어를 모두 활용해야 프로그램이 돌아가는데 많은 이점을 볼 수 있습니다. 그래서 최근에 많은 프로그래밍 언어에서 동시성과 병렬 프로그래밍을 지원하고 있습니다. 병렬 프로그래밍에는 다양한 방법이 있는데, 그 중 오늘은 Async IO, 비동기적 IO에 대해 설명하겠습니다. Async IO란? Async IO의 정의 그럼 Async IO란...
-
Dilworth's Theorem
Introduction 딜워스의 정리(Dilworth’s Theorem)는 부분 순서 집합(partially ordered set)에서 최대 반사슬(antichain)의 크기는 사슬 분할의 최소 개수와 같다는 정리입니다. 먼저 용어들을 설명하겠습니다. 부분 순서 집합이란 말 그대로 순서가 부분적으로 정의된 집합입니다. 예를 들어 자연수 집합 $S$에서 $x$가 $y$로 나누어 떨어질 때 $x\geq y$로 정의하는 경우 $S$를 부분 순서 집합이라고 생각할 수 있습니다. 여기서 6과 3은 비교 가능하지만 6과 5는 비교 불가능합니다. 다른 예시는 2차원 좌표를 원소로 하는 집합에서 $x_1\leq x_2,y_1\leq y_2$이면 $(x_1,y_1)\leq(x_2,y_2)$로 정의하는 것입니다. 여기서는 (1,5)와...
-
BFV scheme에 대한 소개 - 2
Introduction 저번 글에서 BFV scheme에 대해서 소개하는 글을 썼습니다. 이 글에선 저번 글에서 사용한 notation들을 따와서 설명을 할 것이기 때문에, 이전 글을 다시 한번 읽고 오시면 이해가 더 쉬울 것입니다. 이번 글에서는 BFV scheme의 실제적인 구현을 위한 알고리즘들을 좀 더 설명하는 글을 쓰도록 하겠습니다. 이 글에서 사용한 Microsoft SEAL의 코드 구현은 이 글이 쓰여진 시점에서 최신 version의 SEAL(206648d)의 구현을 따릅니다. RNS representation Definition 본격적으로 설명하기에 앞서, RNS representation에 대해 먼저 설명을 하도록 하겠습니다. RNS(Residue Number...
-
Suffix Automaton
Suffix Automaton 문자열의 부분문자열에 대한 복잡한 문제를 풀 때 Suffix Array와 같은 접미사 구조 는 아주 강력한 도구가 된다. SCPC 2021 3번, 서울 리저널 2022 H 등 여러 중요한 대회에서도 이러한 접미사 구조를 응용한 문제들이 정말 많이 나온다. 한국에서 많은 사람들이 알고 있는 접미사 구조로는 Suffix Array 가 있다. Suffix Array는 모든 문자열의 접미사를 정렬한 순열로, 흔히 부분문자열 탐색 쿼리를 빠르게 처리하거나 두 접미사의 LCP를 구할 때 많이 쓰인다. 문자열 접미사 구조 중 알려진 자료구조는...