-
Advanced Graph Algorithms and Optimization: Convexity and Second Derivatives, Gradient Descent and Acceleration
Advanced Graph Algorithms and Optimization: Convexity and Second Derivatives, Gradient Descent and Acceleration 2021년 발표된 Minimum Cost Flow가 Almost-Linear Time에 풀린다는 결과는 현대적인 Convex Optimization 기법들이 전통적인 알고리즘 문제를 해결하는 아주 강력한 도구를 제공함을 보여주는 상징적인 순간이라고 할 수 있다. 요즘은 기계 학습의 인기가 워낙 엄청나기 때문에 Convex Optimization은 대개 기계 학습의 관점에서 다뤄지지만, Convex Optimization은 현대 전산학 전반에 있어서 중요도가 아주 높으며, 그래프 알고리즘적인 관점에서 Convex Optimization을 다뤘을 때 얻어갈 수 있는 것이 아주...
-
Size of struct
서론 이 글은 구조체를 사용할 때 구조체가 차지하는 메모리가 어떻게 계산되는지를 다룬다. Problem Solving을 할 때 조금이나마 도움이 되기를 바란다. 구조체의 메모리 계산 예시 PS가 아닌 개발을 목적으로 한 프로그래밍을 할 때에는 보통 가독성을 중요하게 생각한다. 다음과 같은 c++ 코드를 생각해 보자. const int SIZE = 1000000; struct User{ char sex; short age; long long id; } db[SIZE]; 유저의 성별, 나이, 고유한 id를 설정해야 하는 상황이다. 우선 위와 같이 설정한 이유를 간략히 설명하겠다. 성별은 ‘M’...
-
Linear-Time Encodable Linear Code
Error-correcting code $[n, k, d]$ code: 길이 $k$인 message $m$을 길이 $n$인 codeword $Enc(m)$으로 인코딩하는 $Enc$에 대해, 서로 다른 두 message의 codeword의 hamming distance (서로 다른 entry의 개수)가 항상 $d$ 이상일 때 이를 $[n, k,d]$ code라 합니다. 이 때 가장 가까운 두 codeword가 서로 다른 비율을 나타내는 $\Delta = \frac{d}{n}$을 code의 relative distance라고 부릅니다. Example: Repitition code 예를 들어, “0101”을 “000111000111”로 encoding하는, 원래의 비트를 세 번씩 반복하는 repitition code의 경우 이는 $[3k, k, 3]$ 코드이고,...
-
sweepline MO
개요 다음 문제를 생각해 봅시다. Static Range Inversions Query 길이가 $N$인 수열 $A = (A_1, A_2, \dots, A_{N})$가 주어지면, 다음 $Q$개의 쿼리를 수행해야 합니다. $(1 \leq N \leq 10^5, 1 \leq Q \leq 10^5, 0 \leq A_i \leq 10^9)$ $1 \leq l \leq r \leq N$을 만족하는 $l,r$이 주어지면, $l \leq i < j \leq r, A_i > A_j$ 를 만족하는 $(i,j)$쌍(=inversion)의 개수를 출력한다. 이 글에서는 다음의 내용들을 다룰 것입니다. Static Range Inversions Query 문제를...
-
Multi-Armed Bandit and UCB Algorithm
소개 이 글에서는 불확실성 속에서 좋은 선택을 찾아내야 하는 문제인 Multi-Armed Bandit 문제가 무엇인지 소개하고, 이를 해결하는 알고리즘 중 하나인 UCB 알고리즘을 최대한 쉽고 직관적인 방식으로 유도하고 증명할 것입니다. 기초적인 확률론과 통계학 (ex. 확률분포, 기댓값, 모평균 표본평균)에 대한 지식이 필요하지만 그 외의 배경지식이 없는 사람도 이해할 수 있게 작성했습니다. 문제 설명 돈을 주는 기계? 당신 앞에 2개의 버튼이 달린 기계가 있습니다. 놀랍게도, 이 기계는 버튼을 누르면 돈이 나옵니다! 그리고 운 좋은 당신은 어느 쪽이든 버튼을...