결국 오고야 마는 것들

dp + 슬라이딩 윈도우 문제. 나는 좀 디테일이 부족한 것 같다. 처음에 3번이 아니라 n번 읽어서 틀리고 마지막 결과 출력할 때 n+1이 아니라 n-1로 했다가 틀리고... 문제를 꼼꼼히 읽는것만큼 코드도 꼼꼼히 짜는 연습을 해야겠다... #include #include using namespace std; int cache[6][2], arr[3]; int main(){ ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; for(int i = 0; i > cache[i][0]; cache[i+3][0] = cache[i][0]; } for(int i = 1; i > arr[0] >> arr[1] >..

혼내주기 2021. 8. 1. 23:06

이분 탐색은 뭐랄까 별로 어렵지 않고 방법도 간단한데 어디로 미는지, 어디까지 밀어야하는지가 항상 헷갈린다. 공부가 부족한 탓이겠지,,, 난이도가 비교적 높게 책정된 것 같다. #include #include using namespace std; using ll = long long; int rules[10000][3]; int main(){ ios::sync_with_stdio(0); cin.tie(0); int n, k, d; cin >> n >> k >> d; for(int i = 0; i > rules[i][0] >> rules[i][1] >> rules[i][2]; } int s = 0, e = n+1; while(s < e){ int mid = (s+e)/2; ll..

혼내주기 2021. 8. 1. 23:05

슬라이딩 윈도우 + pq/deque 문제. 내가 푼 방법은 우선순위 큐에 값과 인덱스를 넣어서 매번 범위에서 벗어난 최솟값을 비우고 유효한 최솟값을 출력하는 방식이었다. 근데 다른 사람들의 풀이를 보니 덱을 이용하면 최대 사이즈를 l개로 유지하면서도 풀 수 있길래 바꿔보았다. 확실히 pq는 범위에서 벗어난 얘들이 큐에 남아서 메모리를 많이 차지하는 반면 덱은 메모리를 반밖에 사용하지 않는다. 생각해보니 pq로 풀면 슬라이딩 윈도우라고 하기도 뭐한 것 같다... 비교 - 아래가 우선순위 큐를 이용한 풀이, 위가 덱을 이용한 풀이 덱 #include #include using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0); int n, l, ..

혼내주기 2021. 8. 1. 23:04

유니온 파인드 공부를 시작했다. 각각의 파티마다 사람들을 다 유니온 하고 저장한 뒤, 각 파티마다 진실을 아는 사람이 한명도 없는 파티의 개수를 센다. #include #include using namespace std; int secret[51], parent[51]; vector parties[51]; int find(int u){ if(parent[u] == u) return u; return parent[u] = find(parent[u]); } void merge(int u, int v){ u = find(u); v = find(v); if(u == v) return ; parent[u] = v; } int main(){ ios::sync_with_stdio(0); cin.tie(0); int ..

혼내주기 2021. 8. 1. 23:03

유니온 파인드를 이용해 한명의 친구로 퉁칠수 있는 각 집합의 최소 친구비를 구한뒤, 가진 돈과 비교해서 결과를 출력하면 된다. #include #include #include using namespace std; int cost[10000], parent[10000], minCost[10000]; int find(int u){ if(parent[u] v) swap(u, v); parent[u] += parent[v]; parent[v] = u; } int main(){ i..

혼내주기 2021. 8. 1. 23:02

이 문제는 작년 PS를 시작하기 전 ICPC 예선에서 0솔을 하면서 봤던 문제 중 하나다. 그땐 보자마자 brute force로 다 확인하는 알고리즘으로 짜서 틀렸고, 어떻게 푸는지 감도 못잡았다. 다시 보니 유니온 파인드를 이용하는 것만 발견하면 간단한 문제다. #include using namespace std; int parent[500000]; int find(int u){ if(u == parent[u]) return u; return parent[u] = find(parent[u]); } bool merge(int u, int v){ u = find(u); v = find(v); if(u == v) return true; parent[u] = v; return false; } int main(..

혼내주기 2021. 8. 1. 23:01

유니온 파인드. 이름은 unordered_map을 이용해서 고유 번호를 부여하고 union하는 과정에서 각 집합의 크기를 유지하는 부분을 추가해주면 쉽게 풀린다. #include #include #include #include using namespace std; int parent[200000]; int find(int u){ if(parent[u] < 0) return u; return parent[u] = find(parent[u]); } int merge(int u, int v){ u = find(u); v = find(v); if(u == v) return parent[u]; parent[u] += parent[v]; parent[v] = u; return parent[u]; } int main..

혼내주기 2021. 8. 1. 23:01

문제를 보고 pq로 뽑은 수에 모든 소수를 곱해서 다시 넣어야 겠다는 생각은 했는데, 계속 메모리 초과가 났다. 생각해보니 중복해서 들어가는 수랑 범위를 벗어난 수가 너무 많아보여서 set으로 중복을 제거하고 int 범위 벗어난 수는 다 거르고 넣었는데 메모리 초과가 나왔다. 아마 set에 int 범위 내의 숫자가 너무 많이 들어가서 그런 것 같다. 그래서 set을 없애고 중복을 거르기 위해서 이전에 뽑은 수와 현재 수가 같으면 스킵하는 방식으로 구현하니 메모리 100mb를 사용하고 통과했다. 다른 사람의 코드를 찾아보니 pq에 넣을 때 if(num % arr[i] == 0) break; 한줄만 넣어주면 애초에 중복되는 수를 넣지 않게 되어 메모리와 시간이 압도적으로 절약된다. 뭐랄까 하나만 알고 둘을 ..

혼내주기 2021. 8. 1. 22:59