메모장

stl pow() : 반환 값이 double로 나온다. 항상 유의나이브한 반복문 풀이 : O(N) -> 시간초과 주의분할정복 풀이 : O(logN) -> 베리 굿 #include using ll = long long;//constexpr ll MOD = 1'000'000'007;ll p(ll n){ ll x = 2; ll res = 1; while(n) { if(n&1) { res *= x; //res %= MOD; } x *= x; // x %= MOD; n = n>>1; } return res;}int main(){ cout 주석 부분은 문제에서 모듈로 연산을 필요로 할 때 사용 (오버플로 방지용)

#include using namespace std;using pi = pair;using ll = long long;using pl = pair;using pip = pair;using pdp = pair;constexpr int dy[] = {0, 0, -1, +1};constexpr int dx[] = {-1, +1, 0, 0};constexpr int LIMIT = 1e5 + 2;ll A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z;int main(){ cin.tie(0)->sync_with_stdio(0); }

개요 https://www.acmicpc.net/problem/10090 10090번: Counting Inversions A permutation of integers from 1 to n is a sequence a1, a2, ..., an, such that each integer from 1 to n is appeared in the sequence exactly once. Two integers in а permutation form an inversion, when the bigger one is before the smaller one. As an example www.acmicpc.net 알아두면 좋을 것 같은 유형 (P5) 본문 요약하면 순열에서 역전된 쌍의 개수를 찾는 문제이다. N이 ..

개요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세그먼트 트리 기초 문제 (G1)풀이Range Sum Query를 처리하는 Segment Tree를 구현하면 된다.Ai의 범위가 약 ±2^63 이기 때문에 자료형 주의 ! 코드더보기#include using namespace std; using ll = long long; class segment_tree{ private: vector tr..

매일 상상만 하던 random access + O(logN) 삽입 삭제가 이미 있다니 . . (only g++) #include #include #include using namespace __gnu_pbds; using namespace std; #define ordered_set tree int main(){ ordered_set oSet; // idx 번째 iterator 반환 oSet.find_by_order(idx); // value의 idx를 반환 (value보다 작은 원소 개수를 반환) oSet.order_of_key(value); oSet.insert(v); oSet.erase(v); } 활용 https://www.acmicpc.net/problem/2517 2517번: 달리기 첫째 줄에는..

개요 https://www.acmicpc.net/problem/3015 3015번: 오아시스 재결합 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람 www.acmicpc.net P5 자력솔 ! 본문 힌트 스택을 활용 같은 키가 연속으로 push되는 경우를 고려 풀이 더보기 스택 자료구조를 활용하여 입력을 받음과 동시에 top과 비교하여 처리 (선행 문제 : BOJ 2493번 탑) top이 더 클 경우 : result += (pop한 개수 + 1)개 후 push(키, 1(연속 1회를 의미)) top과 같을 경우 : result += (pop한 ..

보호되어 있는 글입니다.

https://dreamhack.io/learn/quiz/25

General Purpose Register rax (accumulator register) 함수의 반환 값 rbx (base register) x64에서는 주된 용도 없음 rcx (counter register) 반복문의 반복 횟수, 각종 연산의 시행 횟수 rdx (data register) x64에서는 주된 용도 없음 rsi (source index) 데이터 원본 포인터 rdi (destination index) 데이터 목적지 포인터 rsp (stack pointer) 스택 포인터 rbp (stack base pointer) 스택 바닥 포인터 rip : Instruction Pointer Flag Register CF(Carry Flag) ZF(Zero Flag) SF(Sign Flag) OF(Ove..

개요 https://www.acmicpc.net/problem/22953 22953번: 도도의 음식 준비 첫째 줄에 요리사의 수 $N$ ($1 \le N \le 10$), 만들어야 할 음식의 개수 $K$ ($1 \le K \le 1\,000\,000$), 격려해줄 수 있는 횟수 $C$ ($0 \le C \le 5$)가 주어진다. 둘째 줄에 길이가 $N$인 정수 수열 $A$가 주어 www.acmicpc.net G4 본문 처음에는 정렬 후 빠른 순으로 그리디써서 때려 맞춰봤는데, 오답 - 요리사 수와 격려 기회가 생각보다 작다. -> 브루트포스 모든 경우의 수를 확인하면서 이분 탐색으로 최소 시간을 구했다. 그 중 가장 작은 시간을 출력 더 이상 격려 할 수 없는 경우도 고려해야 함에 주의 코드 #inclu..