-
SCLI Framework and its Applications on Minimax Problems
Introduction Machine Learning, Artificial Intelligence의 가장 기본적인 구조는 주어진 데이터에 대한 loss function을 만들고, 이를 최소화하는 것입니다. loss function $f$를 design 했다면, 이 $f$를 최소화하는 것은 최적화 알고리즘의 영역에 들어오게 됩니다. 특히, ML/AI 분야에서는 $f$를 최소화하기 위하여 그 gradient $\nabla f$를 사용하는 gradient-based optimization을 주로 사용합니다. 이러한 환경에서, 최적화 알고리즘을 연구하는 사람들이 자연스럽게 최적화 알고리즘에 대하여 주로 관심을 가지게 되는 정보는 크게 다음과 같습니다. $f$에 대한 특정 조건이 주어졌을 때, 주어진 알고리즘이 얼마나 빠르게 최적해로...
-
Parallel Binary Search
이 게시글은 이분 탐색에 대한 지식을 필요로 합니다. 그리고 union-find, segment tree 자료구조에 대해 알고 있으면 좋습니다. 아래 문제를 봅시다. 제한된 메모리(링크) 길이 $N$의 배열 $A$에서, $q$번째로 작은 원소를 구하는 쿼리를 여러 번 해결하는 문제입니다. 하지만, 문제 지문에 나와 있듯이, 이 문제의 메모리 제한은 4MB로 $A$에 대한 메모리를 할당할 수 없습니다. 하나의 쿼리에 대해 해결해 봅시다. $f(a) =$ 배열 $A$에서 $a$ 이하인 수의 개수라고 합시다. $f(a) \geq q+1$인 경우, $q$번째로 작은 원소는 $a$ 이하입니다. 함수...
-
Gauss-Jordan Elimination
개요 Gauss-Jordan Elimination(가우스 조던 소거법)은 미지수 $x_1$, $x_2$, $…$, $x_m$에 대한 $n$개의 일차방정식으로 구성된 연립일차방정식을 푸는 방법입니다. 해가 존재하는지, 존재한다면 유일한지 판단하고 그 중 하나의 해를 구할 수 있습니다. 연립일차방정식과 행렬 다음과 같은 연립 일차방정식을 생각해봅시다. \[a_{11}x_1 + a_{12}x_2 + ... + a_{1m}x_m = b_1 \\ a_{21}x_1 + a_{22}x_2 + ... + a_{2m}x_m = b_2 \\ \vdots \\ a_{n1}x_1 + a_{n2}x_2 + ... + a_{nm}x_m = b_n\] 이 때, 각 일차방정식의 계수들과 미지수, 상수항을 묶어...
-
Data Structure For Range Mode Query
Table Of Contents Introduction Hardness Result First Method Second Method Third Method Final Method Introduction 안녕하세요, Aeren입니다! Competitive programming을 해본 적 있는 분이라면 range sum query, range minimum query 등등의 다양한 range query문제를 접해보셨을 것입니다. 많은 range query problem들은 linear memory만으로 sublinear time query를 가능하게 해주는 data structure가 존재합니다. 이번 글에서는 비슷한 맥락의 range mode query 를 해결하는 linear memory data structure에 대해 알아 볼 것입니다. 이 글은 다음 논문을 바탕으로 작성되었습니다. Array 혹은 multiset...
-
Wireless Digital Communication 1
서론 무선 통신 시스템은 현대 사회에서 없어서는 안될 시스템입니다. 음성 통신을 위한 휴대전화부터 인터넷을 사용하는 것까지 저희가 실생활에서 겪는 수많은 일에 무선 통신이 반드시 필요합니다. 그렇다면 어떻게 A라는 사람이 전송한 데이터가 수백 km 떨어져있는 B라는 사람에게 정확하게 도착할 수 있을까요? 앞으로 오랜 시간에 걸쳐서 이 질문에 대한 대답을 해보려고 합니다. 이 시리즈가 총 몇 개의 글로 이루어질지는 정확히 예측이 안되지만, 최종적으로는 현재 LTE, 5G 시스템에서 사용되는 OFDM 방식을 설명하는 것을 목표로 하고자합니다. 우선 첫 글에서는...