본문 바로가기

알고리즘225

CSES PS - nearest smaller values(NSV) https://cses.fi/problemset/task/1645/ 하나의 새로운 알고리즘, O(n) 카르테시안 트리라는 자료구조 구현의 기본 아이디어라고 함. https://wcipeg.com/wiki/All_nearest_smaller_values 영어설명 monotonic stack이라고도 함. https://www.acmicpc.net/problem/17298 다른 기본문제 최대 2e5개의 숫자를 입력받으면서, 처음부터 입력받은 그 시점까지 입력받은 숫자보다 작은 수 중에 가장 가까운 값의 인덱스를 반환하라. 1. k> n; stack s; s.push(0); for (int i = 1; i > a[i]; //입력받은 배열의 값보다 큰 값들은 없애버림 while (a[s.top()] >= a[i].. 2020. 1. 16.
CSES PS - Towers (그리디, sorting) https://cses.fi/problemset/task/1073 sorting and searching으로 분류된 것으로 볼때, 무작위 크기를 순서대로 multiset에 넣으면서 처리하는 것에 주목하라는 의미인 듯 하다. 큐브를 이용해서 타워를 쌓을 것이다. (큰 큐브 위에 작은 큐브를 올리거나, 새로운 타워의 기반으로 사용하거나) n개의 큐브의 크기가 주어질 때, 모든 큐브를 사용해서 만들 수 있는 타워의 최소개수를 구해라. (반드시 입력 순서대로 처리해야 한다.) i번째 큐브를 이용해서 타워를 쌓을 땐, 그보다 약간 큰 큐브 위에 두는 게 최적이다. int main() { FAST; int n; cin >> n; multiset st; while (n--) { int a; cin >> a; auto.. 2020. 1. 13.
multiset insert : log erase(iter) : 1 erase(val) : log lower_bound(val) : log *자체적으로 lower_bound가 있다 *ms : 1 2 2 2 3 // ms.erase(2) -> ms : 1 3 erase로 다지워버린다. *erase로 단 하나만 지우려면 ms.erase(b.lower_bound(2)) : log시간에 가능 2020. 1. 11.
codeforces 613 div2 D - Dr. Evil Underscores (분할정복) https://codeforces.com/contest/1285/problem/D 코포에서 분할정복 처음 풀어봐서 코드만 남겨둠 최대 1e5개의 숫자를 입력받는다. 이 숫자들과 임의의 수 X를 xor할 때 가장 큰 ai xor X의 값이 가장 작도록 X를 구해라 코드로 대체 #include #include #include #include #include #include #include #define FAST ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); using namespace std; const int MAX = 1e5 + 5; int n, a[MAX]; int minV(int st, int en, int bt) { int mid = -1; for (.. 2020. 1. 11.

티스토리툴바