-
서로 다른 수와 쿼리
개요 다음 문제를 생각해 봅시다. 수열과 쿼리 5 길이가 $N$인 수열 $A_1, A_2, \cdots, A_N$과 쿼리 $Q$개가 주어집니다. $i$번 쿼리마다 $l_i, r_i$가 주어지면, $[l_i,r_i]$ 구간에 존재하는 서로 다른 수의 개수를 구해야 합니다. ($1 \leq N \leq 10^5, 1 \leq Q \leq 10^5, 1 \leq A_i \leq 10^6, 1 \leq l_i \leq r_i \leq N$) 위 문제(이하 서로 다른 수와 쿼리 문제)는 problem solving을 하다 보면 가끔 맞닥뜨리게 되는데, 유명한 문제인 만큼 $O(N\sqrt{Q})$나 $O((N+Q)\log{N})$등의 다양한 풀이...
-
Wireless Digital Communication 2
서론 지난 글에서 아주 기본적인 (noise가 없는) Binary modulation / demodulation에 대해서 알아보고, 현재 통신 시스템에서 가장 쉽게 볼 수 있는 AWGN 채널에 대해서 간략하게 알아보았습니다. 이번 글에서는 지난 글에서 짧게 언급한 AWGN 채널에 대해 좀 더 자세히 다룰 예정입니다. 또한 AWGN 채널에서의 Binary modulation / demodulation에 대해서 데이터가 잘못 전송될 확률을 구하고, 기존 Binary에서 이를 M개의 bit로 확장시킨 M-ary modulation / demodulation에 대해서 알아보도록 하겠습니다. 본론 AWGN 채널 지난 글에서 작성한 내용을 잠깐 언급하고...
-
Zero Knowledge Proof using AES
1. Introduction 이전에 썼던 글들을 통해 MPC를 이용해 Zero-Knowledge Proof를 만들 수 있다 Fiat-Shamir Transform을 이용해 Zero-Knowledge Proof을 Non-Interactive로 변경할 수 있다 NIZK를 통해 전자 서명을 만들 수 있다 는 것을 알게 되었습니다. 이미 RSA 혹은 ECC 등을 이용한 전자서명이 존재하지만 RSA 혹은 ECC 등은 아직 증명되지 않은 정수론/대수학적 안전성을 가정해야 하는 반면, MPC를 이용한 전자서명은 오로지 해시 함수의 안전성에만 의존한다는 장점이 있습니다. 더 나아가 양자컴퓨터가 개발된 이후에도 안전한 양자 내성 성질을 가지고 있습니다. 전자서명을...
-
알고리즘 문제 접근 과정
알고리즘 문제 접근 과정 알고리즘 문제 풀이를 진행하면서, 어느정도 순간에서부터는 내가 모르는 알고리즘 및 자료구조가 필요하다는 점에서 문제 풀이의 어려움을 느끼게 됩니다. 더 발전하기 위해서 다양한 내용들을 찾아서 공부하고 이를 구현하는 방법을 익히는 과정이 필요하게 됩니다. 하지만 처음 공부할 때에 실제로 제가 가장 많이 겪었던 문제, 혹은 다른 사람들이 처음 공부를 시작 하면서 어려웠던 점들에 대해 이야기를 들을 때에 공통적으로 나왔던 부분은 바로, 알고리즘과 자료구조를 알고 있어도, 해당 문제를 어떤 알고리즘과 어떤 자료구조를 사용해야 하는지...
-
Suffix Array and LCP Array
접미사(Suffix) 문자열 $s$의 $i$번째 접미사란, $s$의 $i$번째 글자부터 마지막 글자까지 포함하는 부분문자열을 뜻합니다. 예를 들어, $s=\mathsf{GATAGACA}$의 접미사를 순서대로 나타내면 다음과 같습니다. \[\begin{array}{|c|c|} \hline \mathsf{i} & \mathsf{suffix} \\ \hline \begin{array}{c} \mathsf{0} \\ \mathsf{1} \\ \mathsf{2} \\ \mathsf{3} \\ \mathsf{4} \\ \mathsf{5} \\ \mathsf{6} \\ \mathsf{7} \end{array} & \begin{array}{l} \mathsf{GATAGACA} \\ \mathsf{ATAGACA} \\ \mathsf{TAGACA} \\ \mathsf{AGACA} \\ \mathsf{GACA} \\ \mathsf{ACA} \\ \mathsf{CA} \\ \mathsf{A} \end{array} \\ \hline \end{array}\] 접미사 배열(Suffix Array) 접미사들을 사전 순으로 나열한 배열이 접미사...