-
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 방식을 설명하는 것을 목표로 하고자합니다. 우선 첫 글에서는...
-
Incremental Topological Ordering and Strong Component Maintenance
Incremental Topological Ordering and Strong Component Maintenance 방향 그래프 $G$ 에 대해서, $G$ 의 위상 정렬 $O: V \rightarrow [n]$ 은 모든 간선 $u \rightarrow v$ 에 대해서 $O(u) < O(v)$ 가 성립하는 순열로 정의된다. $G$ 의 위상 정렬이 존재하기 위해서는 $G$ 가 사이클이 없어야 한다는 사실이 잘 알려져 있다 (Directed Acyclic Graph, DAG). 위상 정렬은 방향 그래프에서 사용하는 가장 기초적인 알고리즘 중 하나이다. 그래프는 일반적으로 순서가 없이 표현되는데, 문제를 풀거나 처리를 하는 데 있어서...