본문 바로가기

C++

 (45)
[BOJ 11003] 최솟값 찾기 - 모노톤 큐 없이 O(n) https://www.acmicpc.net/problem/11003 11003번: 최솟값 찾기N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다.www.acmicpc.net 최솟값 찾기는 모노톤 큐를 사용해 푸는 풀이가 보편적인데 모노톤 큐를 사용하지 않는 \(O(n)\) 풀이를 소개하겠습니다. 1. 배열을 k개씩 묶음으로 쪼개 각각 묶음에서 prefix min, suffix min을 구한다.2. min(prefix_min[i], suffix_min[i - k + 1])을 출력한다. i mod k = 0인 i는 i - k + 1 = 0) ..
[BOJ 1762] 평면그래프와 삼각형 https://www.acmicpc.net/problem/1762 1762번: 평면그래프와 삼각형첫째 줄에 두 정수 N, M이 주어진다. M은 간선의 개수를 나타내는 0 이상의 정수이다. 다음 M개의 줄에는 각 간선이 연결하는 서로 다른 두 정점의 번호가 주어진다. 같은 간선이 중복되어 입력으www.acmicpc.netTag : sqrt? 문제요약 평면그래프 G(v, e)가 주어질 때 크기가 3인 사이클의 개수를 구하라. 풀이 sol 1) 평면그래프는 \( |E| \leq 3|V| - 6 \)을 만족하기 때문에 m은 최대 \(300000 - 6\)입니다. 가장 직관적인 풀이를 생각해보겠습니다. 모든 간선 (i -> j)를 순회하며 (i -> k), (j -> k) 가 모두 존재하는 k의 개수를 세어주고 ..
[BOJ 1801] 직사각형 만들기 https://www.acmicpc.net/problem/1801 1801번: 직사각형 만들기 첫째 줄에 막대의 개수 N이 주어진다. N은 4보다 크거나 같고, 16보다 작거나 같은 자연수이다. 둘째 줄에 막대의 길이가 공백을 사이에 두고 주어진다. 막대의 길이는 10보다 작거나 같은 자연수 www.acmicpc.net Tag : knapsack, optimization 문제요약 주어진 막대를 조합해 만들 수 있는 가장 큰 직사각형의 넓이를 구하라. \((N \leq 16)\) 풀이 직관적으로 떠올릴 수 있는 풀이는 다음과 같다. D[a][b][c][d] = 막대를 중복되지 않게 합쳐 a, b, c, d를 만들 수 있는가 이때 시간복잡도는 \(O(N \times 80^4) = 655360000 \)이 될..
[BOJ 16583] Boomerangs https://www.acmicpc.net/problem/16583 16583번: Boomerangs Let G = (V, E) be a simple undirected graph with N vertices and M edges, where V = {1, . . . , N}. A tuple is called as boomerang in G if and only if {(u, v),(v, w)} ⊆ E and u ≠ w; in other words, a boomerang consists of two edges which shar www.acmicpc.net Tag : constructive, greedy 문제요약 양방향 그래프 G(v, e)를 인접한 2개의 간선들로 분할하라. 이 때 인접한 2개의 간선쌍..
Randomize Binary Search Trees, Treap INTRO 잘 아려진 BBST(Balanced Binary Search Tree : 균형이진탐색트리)의 종류로는 rb tree, b tree 등이 있습니다. 그러나 위의 rb tree와 같이 대부분의 연산을 \(O(logN)\)에 처리하는 트리는 동작 자체도 복잡하고 구현량이 많기 때문에 직접 구현해가며 PS에 사용하기 어렵습니다. (stl에 있는 것을 가져다 쓰면 좋겠지만 연산을 변형해야하는 경우도 존재하니까요) 그래서 삽입, 삭제 등의 연산에 amortized \(O(logN)\)의 시간복잡도를 가지며 상대적으로 구현량이 적은 Splay Tree를 가장 많이 사용합니다. 하지만 Splay Tree도 zig-zag step 등 헷갈릴만한 요소가 많아서 저는 Treap을 선호합니다. Treap은 일반적인..
[BOJ 1725] 히스토그램 https://www.acmicpc.net/problem/1725 1725번: 히스토그램 첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 www.acmicpc.net Tag : DSU 풀이 히스토그램은 모노톤 큐, 분할정복, 세그먼트 트리 풀이가 있다는 것이 잘 알려진 문제입니다. 이 히스토그램을 유니온 파인드로도 풀 수 있는데 저는 이 풀이가 가장 쉽고 구현도 편한다고 생각합니다. 일단 (a[i], i)를 관리하는 벡터 v를 만들고 이를 내림차순으로 정렬합니다. 그리고 이를 순회하며 a[i - 1], a[i + 1]을 보며 a[i..
Codeforces Round #766 (Div. 2) https://codeforces.com/contest/1627 Dashboard - Codeforces Round #766 (Div. 2) - Codeforces codeforces.com b치고 좀 어려운 놈이 있었고, c에 그래프 + 구성적, d는 쉬운 정수론... 바람직한 셋이었다. 이번 셋을 잘풀어서 1854 퍼포먼스를 뽑았는데 기분이 좋다. A. Not Shading Tag : 무지성 풀이 (r, c)가 B라면 0, 같은 행 또는 열에 B가 존재한다면 1 아니면 2이다. 전체에 B가 하나도 없다면 -1을 출력하면 된다. 전체코드 #include "bits/stdc++.h" #define endl '\n' using namespace std; using ll = long long; void so..
FastIO 템플릿 #include #include #include template struct FASTIO { char *p,O[2000000],*d; void set() { struct stat st;fstat(0,&st);d=O; p=(char*)mmap(0,st.st_size,1,1,0,0); } ~FASTIO() { write(1,O,d-O); } inline T get() { T x=0;bool e;p+=e=*p=='-'; for(;*p==10 or *p==32;p++); for(char c=*p++;c&16;x=10*x+(c&15),c=*p++); return e?-x:x; } inline void put(T x) { if(d-O+100>2000000) write(1,O,d-O), d=O; if(x

티스토리툴바