-
Rust의 async/await
서론 지난 글에서 다양한 언어에서의 async/await에 대해 알아보았습니다. 이번 글에서는 Rust의 async/await에 대해 더 자세히 알아보겠습니다. std::future Rust의 async/await는 std::future::Future를 기반으로 합니다. std::future::Future trait은 std::future에 정의되어 있습니다. pub trait Future { type Output; fn poll(self: Pin<&mut Self>, cx: &mut Context<'_>) -> Poll<Self::Output>; } Future trait은 poll 함수를 정의하고 있습니다. poll 함수는 Future가 준비되었는지를 확인합니다. Future가 준비되었다면 Poll::Ready를 반환하고, 아니라면 Poll::Pending을 반환합니다. 자세히 살펴보면 poll 함수는 self를 Pin<&mut Self>로 받고 있습니다. Pin의 정의를 볼까요? std::pin::Pin pub...
-
Disjoint Sparse Table
Disjoint Sparse Table은 효율적인 쿼리 처리를 위한 자료구조 중 하나로, 1차원 배열의 range query를 해결하는 데 사용됩니다. 이 자료구조는 $O(N log N)$으로 전처리되며 $O(1)$의 시간복잡도로 range query를 구할 수 있습니다. 일반적인 Sparse Table로 range query를 처리할 때와 같은 시간복잡도를 가지지만, Sparse Table의 경우 쿼리로 찾은 두 구간의 값을 합칠 때 겹치는 부분이 존재하기 때문에 $x \circ x = x$를 만족하는 연산(ex: $max$, $min$, $gcd$)만 가능하지, Disjoint Sparse Table은 그렇지 않은 연산(ex: $+$, $\times$)도 지원합니다. Sparse...
-
구간 최장 증가 부분 수열 쿼리 (Part 1)
이번 글에서는 다음과 같은 쿼리를 수행하는 자료 구조에 대해 다룬다: 길이 $N$ 의 수열 $A$ 와 $Q$ 개의 쿼리 $1 \le i \le j \le N$ 가 주어질 때, $A[i], A[i + 1], \ldots, A[j]$ 의 최장 증가 부분 수열 (Longest Increasing Subsequence, LIS) 를 계산하라. LIS 문제의 경우 동적 계획법으로 해결할 수 있는 가장 기초적인 문제 중 하나로, 수학적으로 여러 의미를 가지기 때문에 변형된 문제들이 다방면으로 연구되고 있다. 위와 같은 쿼리 문제는 다들 자료...
-
A Tree Representation for Failure Function of a String
A Tree Representation for Failure Function of a String Introduction KMP(Knuth-Morris-Pratt) 알고리즘은 주어진 문자열에서 패턴 문자열을 검색하는 전통적인 선형 시간 알고리즘이다. 알고리즘 대회 분야에서도 KMP 알고리즘을 응용하여 해결할 수 있는 문제는 꾸준히 출제되고 있으며, 한국 리저널만 보더라도 2017 Preliminary J번, 2021 Regional K번 등에서 등장한 바가 있다. KMP 알고리즘을 응용하여 해결하는 문제들은 많은 경우 KMP 알고리즘의 중간 단계에서 등장하는 실패 함수(Failure function)에 대한 깊은 이해를 바탕으로 한다. 따라서, 실패 함수가 해당 문자열의 구조에 대해 어떤...
-
SAGE: Saliency-Guided Mixup with Optimal Rearrangements
SAGE: Saliency-Guided Mixup with Optimal Rearrangements Mixed Sample Data Augmentation, MSDA는 vision task에서 사용하는 데이터를 증강하기 위해서 사용되는 기법입니다. 이를 위한 수많은 접근 방법이 나왔으며, Mixup을 필두로 해당 기법이 성능 개선에 큰 효과가 있다는 것이 알려지고, 최근에 왜 이러한 MSDA 방법론들이 실제 성능 향상에 영향을 주는지를 loss function perspective로 설명하는 A Unified Analysis of Mixed Sample Data Augmentation: A Loss Function Perspective이란 논문이 나오면서 더욱 다양한 관점과 방법론으로 연구되고 있습니다. 물론 아직 MSDA 방식이 정말로...