결국 오고야 마는 것들

아직 세그먼트 트리 응용 문제는 너무 어렵다. 하루를 넘게 고민했는데 떠올리지 못해서 다른 블로그를 참고했고, 결국 바로 전에 푼 최솟값 최댓값 세그먼트 트리로 푸는 문제였다. 세그먼트 트리는 구간을 이용한 자료구조라는 점을 기억하면서, 차근차근 공부해야겠다. #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; const int SZ = 1 > k; for(int i = 0; i 0; --i) { minTree[i] = min(minTree[i > b; if(!q) update(a, b)..

혼내주기 2021. 7. 23. 10:56

이리저리 삽질하다가 N이 최대 100000이기 때문에 벡터로 구간 원소를 들고 있으면 되지 않을까 했는데 진짜 통과했다! 알고 보니 이런 세그트리를 머지소트 트리라고 한다. 처음에는 init 과정을 left right 순서대로 넣고 sort했는데, merge함수가 STL에 있길래 참고했다. 이번 문제는 떠올려서 풀어서 기분이 아주 좋다!@@ #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; const int N = 1 num; tree[N+i].push_back(num); } for(int i = N-1; i; --i) { tree[i].reserve(tree[i

혼내주기 2021. 7. 23. 10:55

세그 트리로 k번째 수 찾기. 입력되는 숫자의 범위가 정해져 있다는 사실을 이용해 세그 트리의 leaf node가 각 수의 갯수를 나타내고 parent node들은 자식 노드들의 갯수의 합을 나타내도록 구현하면 된다. query는 binary search처럼 k번째 수를 찾으면 된다. k번째도 그렇고 머지 소트 트리도 그렇고 주어진 입력에서도 많은 정보를 얻을 수 있다. 그저 내 꼼꼼함이 부족할 뿐... #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; int tree[1 n; } int update(int t, int v, int i = 1, int s = 0, int e = (1> 1; return tree..

혼내주기 2021. 7. 23. 10:53

lazy propagation 연습 문제. 기본 세그 트리에 lazy와 propagation을 추가하면 된다. 이름도 직관적이고 방법도 되게 간단한데, 이런 방법을 떠올렸다고 생각하니 대단할 뿐이다... 되게 재미있는 기법인듯. 백준에서는 lazy propagation이 '느리게 갱신되는'으로 번역되어있다. ㅋㅋㅋ #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; using ll = long long; const int N = 1 k; for(int i = 0; i > tree[i+N]; for(int i = N-1; i; --i) tree[i] = tree[i

혼내주기 2021. 7. 23. 10:52

lazy propagation으로 구간 xor를 하는 문제. xor를 홀수번 하면 1번 한 것과 같고, 짝수번 하면 안한 것과 같다는 점을 캐치하는데 오랜 시간이 걸렸다... xor이 어떤 연산인지 머리로는 아는데, 그 의미를 체득하려고 노력중이다. #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; const int N = 1

혼내주기 2021. 7. 23. 10:52

#include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; const int N = 1

혼내주기 2021. 7. 23. 10:51

내 접근법은 트리를 만들고 월급을 출력해야 할 때 해당 노드부터 root 까지 올라가는 path를 저장하고 그 path의 역순으로 update를 해서 propagated 값을 출력하는 방법이었는데 TLE를 받았다. 시초를 받고 생각해보니 트리가 skewed tree일 때 매번 경로를 찾기 위해 O(N)이 걸리기 때문에 그런 것 같다. 도저히 풀이가 안떠올라서 검색하다가 ANZ님의 블로그를 보고 이해했다. range가 없으니 dfs로 해당 노드의 구간을 만들어서 쿼리를 날린다... 구현하고도 dfs로 재정의된 노드 순서를 적용 안해서 또 한참 헤맸다. 세그 문제들은 디버깅이 어렵다. 결국 lazy에 구간 재정의만 해주면 되는 문제였고, 그걸 검색해서 알고도 왜 이렇게 헤맸을까........ 세상에 똑똑한 ..

혼내주기 2021. 7. 23. 10:50

brute force 문제. 처음에 방문 체크를 위해 int cache[1000005][11]; 이런 배열을 선언하고 stoi로 확인했는데, 고수들의 풀이를 보니 set이나 map을 사용했길래 또 한 수 배웠다. 특히 이 문제 같은 경우는 나올 수 있는 경우의 수가 6!밖에 안되기 때문에 메모리를 왕창 아낄 수 있다. 오늘의 교훈: dp는 map hashmap으로도 할 수 있다. #include #define fastio ios::sync_with_stdio(0), cin.tie(0) using namespace std; set cache[11]; int n, m, k, ans = 0; bool able = false; void input() { fastio; cin >> n >> k; } void d(..

혼내주기 2021. 7. 22. 11:00