BOJ (55) 썸네일형 리스트형 [BOJ 12858] Range GCD https://www.acmicpc.net/problem/12858 12858번: Range GCD 첫째 줄에 수열의 원소의 개수를 나타내는 하나의 자연수 N이 주어진다. (1 ≤ N ≤ 100,000) 둘째 줄에 수열의 각 원소를 나타내는 N개의 자연수가 주어진다. i번째로 등장한 자연수는 수열의 i번째 www.acmicpc.net Tag : segment tree 문제요약 구간 업데이트(덧셈)가 있을 때 쿼리마다 구간의 gcd를 구하라. 풀이 a > b일 때 gcd(a, b) = gcd(a, a - b)임이 잘 알려져있습니다. 따라서 gcd(A[l], ... , A[r]) = gcd(A[l], A[l + 1] - A[l], ... , A[r] - A[r - 1])이 성립합니다. 세그먼트 트리의 각 노.. [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.. [BOJ 2042] 구간 합 구하기 https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net Tag : segment tree 풀이 두가지 풀이가 있다. 1. 세그먼트 트리 : \(O(QlogN)\) 2. 누적합 + 변화량만 따로 저장 : \(O(N + Q^2)\) 구간 합 구하기 2에는 simd 펜윅을 박은 분이 1등이던데 이 문제에는 그런 제출이 없어서 다행.. 코드 #pragma GCC optimize ("O3") #prag.. [BOJ 8903] 장비 https://www.acmicpc.net/problem/8903 8903번: 장비 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 N과 K가 주어진다. (1 ≤ N ≤ 10,000, 1 ≤ K ≤ N) 다음 N개 줄에는 0보다 크거나 같고, 10,000보다 작거나 같은 정수 다 www.acmicpc.net Tag : case work 문제요약 장비마다 5개의 능력치가 있는데 장비를 여러개 골랐을 때 각각의 능력치는 고른 장비들에서 최대 하나로만 결정된다. 고를 수 있는 장비의 개수가 주어졌을 때 능력치 합의 최대를 구하라. 풀이 5개 이상 고를 수 있다면 각각의 능력치가 최대인 것을 하나씩 골라오면 된다. 그게 아니라면 \(O(2^{10} \times N)\) 비트마스킹.. [BOJ 16474] 이상한 전깃줄 https://www.acmicpc.net/problem/16474 16474번: 이상한 전깃줄 엘리트 도로설계사 현정이는 도로 위 전봇대 사이에 연결된 전깃줄을 관리하는 일을 한다. 도로 양 옆에는 각 고유번호를 갖고 있는 전봇대가 여러 개 있다. 마을에 최대한 많은 양의 전력을 보 www.acmicpc.net Tag : lis 문제요약 전깃줄의 연결 상태가 입력으로 들어오는데 이 때 전깃줄을 최소한으로 끊어서 전깃줄이 교차하지 않는 상태를 만드는 것이 목표이다. 전깃줄을 끊는 최소 횟수를 구하라. 풀이 입력을 조금만 손보면 \(O(N^2)\) lis 문제가 된다. 전체코드 #include "bits/stdc++.h" #define endl '\n' using namespace std; using ll.. [BOJ 23578] 비 오는 날 https://www.acmicpc.net/problem/23578 23578번: 비 오는 날 피에스고등학교의 교장 이환이는 학교를 매우 사랑한다. 그래서 이환이는 매일 점심시간에 학교의 모든 건물을 돌아다닌다. 비가 오는 어느 날, 이환이는 학교 곳곳을 돌아다니고 싶었지만 비 www.acmicpc.net Tag : greedy 문제요약 스패닝 트리를 만드는데 \( \sum{ (degree_i)^2 * a_i } \)를 최소화해라 풀이 처음에 이상한 전략을 많이 생각했다. 일단 \(a_i\)에 비례하게 분배해놓고 이득이 되는 쪽으로 옮긴다던지.... 그런데 이걸 잘 정리하다보니까 그냥 처음부터 최소화되는 쪽으로 이어가는게 낫다는 결론이 나왔다. 일단 모든 정점에서 \( degree_i \)가 1 이상이라.. [BOJ 10523] 직선 찾기 https://www.acmicpc.net/problem/10523 10523번: 직선 찾기 입력 예제 1에서 (0, 0) / (3, 3) / (10, 10)을 지나는 직선을 찾을 수 있다. 2.75개 이상의 점을 지났으니 그러한 직선이 있다고 볼 수 있다. www.acmicpc.net Tag : random 문제요약 N개의 점이 이차원 좌표평면 위에 있을 때 이 중 p퍼센트 이상의 점을 지나는 직선이 있는지 판별하라. 풀이 답이 possible이면서 시간복잡도 상으로 최악일 경우를 생각해보자. k = \( \lfloor \frac{n \times p}{100} \rfloor \)일 때 k개의 점을 지나는 직선이 딱 1개 있는 경우일 것이다. 서로 다른 두 점을 아무렇게나 한번 골라서 이 두 점을 지나는.. [BOJ 13255] 동전 뒤집기 https://www.acmicpc.net/problem/13255 13255번: 동전 뒤집기 첫째 줄에 동전의 개수 N (1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 K (1 ≤ K ≤ 50)이 주어진다. 셋째 줄에는 A[i] (1 ≤ A[i] ≤ N)가 주어진다. www.acmicpc.net Tag : dp, combinatorics 문제요약 N개의 동전 중 \(A_i\)개를 랜덤으로 골라 뒤집는 작업을 N번 반복한다. 이 때 앞면이 위인 동전 개수의 기댓값을 구하라. 풀이 확률 dp다. 주의할 점이 있다면 경우의 수를 dp의 정의로 잡고 쭉 구해놓고 답을 출력할 때만 표본을 나누면 오버플로우때문에 문제가 된다. (long double에도 안들어간다) 이걸로 30분정도를 맞왜틀했다... \(d.. 이전 1 2 3 4 5 ··· 7 다음
