코드#include #include #include #include using namespace std;// 소수 목록을 저장할 벡터vector prime;// 에라토스테네스의 체로 소수 계산void sieve() { int max_limit = 316; // sqrt(100,000) vector is_prime(max_limit + 1, true); is_prime[0] = is_prime[1] = false; // 0과 1은 소수가 아님 for (int i = 2; i * i > tc; sieve(); // 소수 미리 계산 while (tc--) { int n; cin >> n; map factors; // 소인수와 지수를 저장 ..
전체 글
Hello World1. 온라인 쿼리특징쿼리가 주어지면 즉시 처리하고 결과를 반환해야 한다.입력받은 순서대로 쿼리를 처리한다.실시간 데이터 업데이트나 연속된 요청 처리가 필요한 문제에서 사용사용해야 하는 상황1. 실시간 응답이 필요한 경우사용자가 요청할 때마다 즉시 결과를 반환해야 하는 문제ex) 게임 서버에서 사용자의 실시간 요청 처리2. 데이터가 점진적으로 업데이트 되는 경우데이터가 동적으로 변화하며, 각 쿼리마다 최신 상태를 반영해야 하는 문제ex) 배열 값이 자주 변경되고, 변경된 값을 기반으로 쿼리를 처리하는 경우3. 데이터 크기가 작거나 중간 규모인 경우매 쿼리마다 즉시 처리하더라도 성능 문제가 없는 경우알고리즘 예시세그먼트 트리펜윅 트리2. 오프라인 쿼리특징쿼리를 미리 모아서 일괄적으로 처리한다.쿼리의 순서를 ..
오프라인 쿼리와 Mo's Algorithm오프라인 쿼리는 쿼리를 즉시 처맇지 않고, 미리 저장해 두었다가 특정 ㅈ건에 따라 일괄적으로 처리하는 알고리즘 설계기법을 말한다. 이 방법은 데이터가 많고 쿼리가 많은 상황에서 효율적인 처리를 가능하게 한다. 1. 오프라인 쿼리의 특징즉시 응답하지 않음 - 쿼리를 입력받을 때 바로 처리하지 않고, 나중에 한 번에 처리한다.정렬 기반 최적화 가능 - 쿼리를 정렬하거나 특정 조건에 따라 순서를 조정하여 효율성을 높일수 있다.시간 복잡도 최적화 - 적절한 데이터 구조와 알고리즘을 사용하면 쿼리의 총 실행시간을 줄일 수 있다.2 . 오프라인 쿼리의 장점배치 처리 - 쿼리를 정렬하거나 재구성한 뒤 효율적으로 처리하므로 전체 실행 시간이 줄어든다.특정 패턴 최적화 - 예를 ..
for loop에서 const &auto의 사용for문을 사용하다보면 for(int i : res) 와 같은 문법을 사용할 때가 있다. 그런데 for(const auto& i : res) 문법도 있다. 둘의 차이는 값을 복사해서 넣는지, 참조만 하는지의 차이이다. 이 특성으로 인해 PS에서 시간초과가 날 수도 있다. ranged loopfor(int i : res) cout 위 for loop의 경우에는 res에서 i를 새로 만들어 값을 복사해서 넣는다. 그래서 i = 0과 같은 코드를 시행해도 원본은 바뀌지 않는다. 하지만 값을 복사하기 때문에 그 비용이 든다.for(auto& i : res) cout 위 for loop의 경우는 res의 값을 그대로 참조한다. 그래서 i = 0 명령을 내리면 값이 ..
map과 unordered_map의 차이 mapunordered_map순서오름차순 정렬정렬 없음구현트리 구조해시 테이블탐색 시간log(N)O(1)삽입 시간log(N)O(1) 요약map은 정렬 순서를 보장하고 unordered_map은 보장하지 않는다.unordered_map은 hash 기반으로 map보다 속도가 빠르다.map은 BST(Binary Search Tree) 기반으로 해시 충돌에서 안전하다.set과 unordered_set도 동일하게 각각 트리, 해시 기반이다.multimap과 multiset은 BST 기반이다.참조https://zshchun.github.io/posts/map%EA%B3%BC-unordered-map%EC%9D%98-%EC%B0%A8%EC%9D%B4/
unordered_map과 배열의 성능 차이오프라인 쿼리 문제를 풀다가 unordered_map을 이용하면 시간초과가 나고 배열을 사용하면 시간이 단축되는 경험을 했다. 둘 다 접근할 때 O(1)으로 알고 있었는데, 어디서 차이가 날까 생각해보았다. 해시충돌 때문이라고 넘어갈까 했지만 자세히 알아보고 기록해두는 게 좋을 거 같아서 포스팅하기로 결정했다. 1. unordered_map vs 배열a) unordered_map의 특성시간 복잡도평균적으로 O(1) 시간에 접근 가능핮만 최악의 경우 O(N)으로 느려질 수 있음 (해시 충돌 발생 시)캐시 활용도unordered_map은 내부적으로 해시 테이블을 사용하며 데이터가 메모리 상에 분산되어 저장된다.따라서 캐시 적중률(cache hit rate)가 낮아질..
코드#include #include #include #include #include #include using namespace std;struct Query { int L, R, idx;};const int MAX_N = 300003;int n, c, a[MAX_N], m, max_cnt, max_num, freq[10001];void add(int x) { freq[x]++;}void remove(int x) { freq[x]--;}void FASTIO() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);}int main() { FASTIO(); cin >> n >> c; for (int i = 0; i > a[i]; int blo..
코드#include #include #include using namespace std;typedef long long ll;const int MAX_N = 100003;ll n, q, m, cnt = 0;ll a[MAX_N];vector tree(MAX_N + 1, 0);vector, pair>> queries;vector> updates;vector> res;void update(int idx, ll diff) { while (idx 0) { ans += tree[idx]; idx -= (idx & -idx); } return ans;}void FASTIO() { ios_base::sync_with_stdio(false); cin.tie(NULL)..
코드#include #include #include #include using namespace std;struct Query { int L, R, idx;};const int MAX_N = 100003;int n, q, max_cnt = 0;int arr[MAX_N], freq[200003], cnt[MAX_N];vector queries;vector res;void add(int x) { cnt[freq[x]]--; // 현재 빈도 감소 freq[x]++; // 값의 빈도 증가 cnt[freq[x]]++; // 증가한 빈도 반영 max_cnt = max(max_cnt, freq[x]); // 최대 빈도 갱신}void rem..
코드#include #include #include #include using namespace std;struct Query { int L, R, idx;};const int MAX_N = 100003;int n, q, max_cnt = 0;int arr[MAX_N], freq[200003], cnt[MAX_N];vector queries;vector res;void add(int x) { cnt[freq[x]]--; // 현재 빈도 감소 freq[x]++; // 값의 빈도 증가 cnt[freq[x]]++; // 증가한 빈도 반영 max_cnt = max(max_cnt, freq[x]); // 최대 빈도 갱신}void rem..