본문 바로가기

BOJ

 (55)
[BOJ 27014] Cube Stacking https://www.acmicpc.net/problem/27014 27014번: Cube Stacking Farmer John and Betsy are playing a game with N (1 ≤ N ≤ 30,000)identical cubes labeled 1 through N. They start with N stacks, each containing a single cube. Farmer John asks Betsy to perform P (1≤ P ≤ 100,000) operation. There are two types of ope www.acmicpc.net Tag : DSU 스몰투라지, 세그 등... 뇌절각은 잔뜩 보이는데 그냥 \(O(logN)\) 이하의 유니온 파인드로 생각을 했을 ..
[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 4500..
[BOJ 24978] Subset Equality https://www.acmicpc.net/problem/24978 24978번: Subset Equality The cows are trying out a new method of exchanging coded messages with each-other where they mix irrelevant letters in among relevant letters to make the messages hard to decode. The cows transmit two strings $s$ and $t$ each of length at most $10^5$ consi www.acmicpc.net Sol 1) 메모이제이션 잘한 완탐 문자 집합 A에 대해 정답이 Y라면 A의 부분집합 B는 모두 Y다. N이라면 ..
[BOJ 3392] 화성 지도 https://www.acmicpc.net/problem/3392 3392번: 화성 지도 첫째 줄에 화성탐사선 성화가 보낸 지도의 수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 지도의 정보가 주어진다. 지도의 정보는 네 정수 x1, y1, x2, y2 (0 ≤ x1 < x2 ≤ 30,000, 0 ≤ y1 < y2 ≤ 30 www.acmicpc.net Tag : simd 스위핑하면서 (r-l)/16번 나이브하게 더해줬다. 시복은 \(O(30000^2 / 16) \) 코드 #pragma GCC optimize ("O3,unroll-loops") #pragma GCC target ("avx,avx2,fma") #include #include using namespace std; #de..
[BOJ 13551] 원과 쿼리 https://www.acmicpc.net/problem/13551 13551번: 원과 쿼리 2차원 좌표 평면 위에 점 N개가 있다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. x, y, r: 중심이 (x, y)이고, 반지름이 r인 원의 내부에 점이 몇 개 있는지 출력한다. 원의 둘레 위에 있는 www.acmicpc.net clang으로 냈더니 살짝 커팅한 나이브가 돌더라...ㅋㅋㅋ https://blog.naver.com/jinhan814/222680932977 [jinhan814님 풀이] 코드 #include "bits/stdc++.h" #define endl '\n' using namespace std; using ll = long long; const int di[4] = {0, -1, ..
[BOJ 1762] 평면그래프와 삼각형 https://www.acmicpc.net/problem/1762 1762번: 평면그래프와 삼각형 첫째 줄에 두 정수 N, M이 주어진다. M은 간선의 개수를 나타내는 0 이상의 정수이다. 다음 M개의 줄에는 각 간선이 연결하는 서로 다른 두 정점의 번호가 주어진다. 같은 간선이 중복되어 입력으 www.acmicpc.net Tag : 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개의 간선쌍..

티스토리툴바