-
Knapsack
--- layout: post title: "Knapsack Algorithm의 여러 응용" author: knon0501 date: 2023-03-18 tags: [dynamic-programming] --- Introduction 배낭 문제란 무게제한이 있는 가방에 고유한 무게와 가치를 가지는 물건들을 채워넣을 때 어떻게 해야 최대 가치를 가방에 넣을 수 있을지 계산하는 문제입니다. 무게에 별다른 제한이 없을 경우 물건이 총 $N$개일 때 $O(2^N\times N)$정도의 시간복잡도로 계산할 수 있으며 NP-complete 임이 알려져 있습니다. 물건의 무게가 정수이고 가방의 무게제한이 $W$일 경우 동적계획법으로 $O(NW)$에 해결할 수 있습니다. 이 글에서는 독자가 동적계획법으로 배낭 문제를...
-
BFV scheme에 대한 소개 - 3
Introduction 지금까지 BFV Scheme에 관한 설명글과, BFV scheme의 practical한 구현을 위해서 RNS module이라는 걸 사용한다는 것 그리고, RNS module에서 operations들이 기본적으로 어떻게 돌아가는지에 대해 설명하는 글을 썼습니다. 이번 글에서는 RNS module에서 구현하기 까다로운 연산들을 어떻게 처리하는지에 대해 설명하겠습니다. Backgrounds 저번 글에 좀 더 자세히 설명하고 있지만, Background를 한 번 더 짚고 넘어가겠습니다. RNS module은 널리 알려진 CRT(Chinese Remainder Theorem)에 기반하여 큰 범위의 수를 작은 수 여러 개로 표현하는 방식입니다. Homomorphic Encryption은 보안상의 이유 때문에 대부분...
-
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 문제의 경우 동적 계획법으로 해결할 수 있는 가장 기초적인 문제 중 하나로, 수학적으로 여러 의미를 가지기 때문에 변형된 문제들이 다방면으로 연구되고 있다. 위와 같은 쿼리 문제는 다들 자료...