Problem Solving

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/30690 🧐 관찰 및 접근 # 암튼 트리가 있다 간선 하나를 떼고 다시 연결해서, 가장 많은 간선을 지나가고싶다. 간선 하나를 떼고 다시 연결해서, 트리의 지름을 최대로 하고 싶다. 쪼개진 두개의 트리에서, 각각의 지름 + 1이 답이다. 트리를 쓰는 트리 문제 해당 문제에서, 해당 서브트리를 제외한 트리의 지름을 구할 수 있으면 되는 것 같다. 이는 리루팅과 부모깊이, 다른 자식의 깊이 두개정도를 잘 들고있으면 가능하겠다. 다른 자식의 지름도 들고있어야 한다!! 예제 트리 그림 💻 풀이 # 코드 (C++): int N, Q; vector<int> links[200010]; int depth[200010]; vector<pii> childs[200010]; // {mxDepth, nodeIdx} vector<pii> childs2[200010]; // {mxDiam, nodeIdx} int diam[200010], upDepth[200010], upDiam[200010]; void dfs1(int cur, int par){ vector<pii> ret; ret.push_back({0, cur}); for(auto nxt: links[cur]){ if(nxt == par) continue; depth[nxt] = depth[cur] + 1; dfs1(nxt, cur); diam[cur] = max(diam[cur], diam[nxt]); ret.push_back({childs[nxt][0].first + 1, nxt}); sort(all(ret), greater<pii>()); if((int)ret.size() > 3) ret.pop_back(); childs2[cur].push_back({diam[nxt], nxt}); sort(all(childs2[cur]), greater<pii>()); if((int)childs2[cur].size() > 2) childs2[cur].pop_back(); } childs[cur] = ret; if((int)ret.size() >= 2) diam[cur] = max(diam[cur], ret[0].first + ret[1].first); if((int)ret.size() >= 1) diam[cur] = max(diam[cur], ret[0].first); } void dfs2(int cur, int par, int mxUp){ for(auto nxt: links[cur]){ if(nxt == par) continue; vector<int> candidates; candidates.push_back(mxUp); for(auto [d, idx]: childs[cur]) if(idx != nxt) candidates.push_back(d); sort(all(candidates), greater<int>()); if((int)candidates.size() >= 2) upDiam[nxt] = max(upDiam[nxt], candidates[0] + candidates[1]); if((int)candidates.size() >= 1) upDiam[nxt] = max(upDiam[nxt], candidates[0]); for(auto [d, idx]: childs2[cur]) if(idx != nxt) upDiam[nxt] = max(upDiam[nxt], d); upDiam[nxt] = max(upDiam[nxt], upDiam[cur]); dfs2(nxt, cur, candidates[0] + 1); } } void solve(){ cin >> N >> Q; rep(i, 0, N-1){ int u, v; cin >> u >> v; links[u].push_back(v); links[v].push_back(u); } dfs1(1, -1); dfs2(1, -1, 0); // rep(i, 1, N+1) cout << diam[i] << " "; cout << "\n"; // rep(i, 1, N+1) cout << upDiam[i] << " "; cout << "\n"; while(Q--){ int u, v; cin >> u >> v; if(depth[u] < depth[v]) swap(u, v); cout << diam[u] + upDiam[u] + 1 << "\n"; } } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/23569 번역 문제 번역 # 문제 설명 # 사람들 간의 상호작용이 주어질 때, 정점이 사람들이고 두 사람이 서로 친구인 경우에만 그들 사이에 간선이 있는 그래프를 정의할 수 있습니다. 이러한 그래프를 소셜 네트워크라고 하며, 예를 들어 대학의 학생들이나 작은 마을의 주민들과 같은 모든 사람들의 집합에 대해 잘 정의됩니다. 최근 몇 년간 소셜 네트워크를 분석하는 완전한 과학 분야가 생겨났는데, 이는 사람들과 그들의 행동에 대한 많은 흥미로운 측면들이 이 친구 관계 그래프의 속성으로 가장 잘 이해되기 때문입니다.

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/32144 🧐 관찰 및 접근 # 문제에 내 이름이 나와서 기분이 좋다. 서브트리를 하나 잡아서, 그 서브트리의 루트와 그 부모와의 연결을 끊고 서브트리의 임의의 정점과 방금 끊은 부모를 연결하는 연산을 할 수 있다. 직관적으로, 해당 서브트리에서 줄 수 있는 길이의 가중치가 깊이에서 지름으로 바뀜을 알 수 있다. Tree DP를 이용한 트리의 지름 구하기 방법을 이용하면 좋을 것 같다. 위와 같은 경우같은게 발생할 것 같다. 두번째로 작은 트리의 지름과 마찬가지로, 기존 지름의 양 끝 점중 한 점은 유지된다. …인줄알았는데 안된다. 다음과 같이 서브노드 안에 기존 트리의 지름이 다 있는 경우도 있다… 결국 문제에서도 말하는 것처럼 문제를 부분트리와 그 나머지로 보면, 리루팅이 가능하지 않을까? 리루팅을 이용해서, 다음과 같은 정보를 저장하자. 서브트리의 지름 해당 서브트리에서 가장 깊은 깊이 두개 (리루팅용) 해당 노드에서 위로 갔을때, 가장 깊은 길이 이는 dfs를 이용해서 구현 가능하고, 시간복잡도는 $O(N)$이다. 디버깅을 위한 예제 2번 그림 💻 풀이 # 코드 (C++): int N; vector<int> links[300005]; vector<pii> max_depth[300005]; int diam[300005]; int updepth[300005], updiam[300005]; vector<pii> dfs(int cur, int par){ vector<pii> v; v.push_back({0, cur}); for(auto nxt: links[cur]){ if(nxt == par) continue; auto nv = dfs(nxt, cur); diam[cur] = max(diam[cur], diam[nxt]); v.push_back({nv[0].first + 1, nxt}); sort(all(v), greater<pii>()); while(v.size() > 2) v.pop_back(); } if(v.size() >= 2) diam[cur] = max(diam[cur], v[0].first + v[1].first); else diam[cur] = max(diam[cur], v[0].first); max_depth[cur] = v; // cout << "cur: " << cur << " diam: " << diam[cur] << " max_depth: "; // for(auto p: v) cout << "(" << p.first << "," << p.second << ") "; // cout << '\n'; return v; } void dfs2(int cur, int par){ for(auto nxt: links[cur]){ if(nxt == par) continue; updepth[nxt] = updepth[cur] + 1; if(max_depth[cur][0].second != nxt) updepth[nxt] = max(updepth[nxt], max_depth[cur][0].first + 1); else if(max_depth[cur].size() >= 2) updepth[nxt] = max(updepth[nxt], max_depth[cur][1].first + 1); dfs2(nxt, cur); } } void solve(){ cin >> N; rep(i, 2, N+1){ int p; cin >> p; links[p].push_back(i); links[i].push_back(p); } dfs(1, -1); dfs2(1, -1); rep(i, 2, N+1) cout << max(diam[1], updepth[i] + diam[i]) << "\n"; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/19581 🧐 관찰 및 접근 # 가중치 없는 트리인줄 알고, 당연히 지름-1이 답이 아닌가? 했더니 가중치가 있었다 가중치가 있는 트리라면, 우리가 원래 쓰던 DFS두번이라는 방법은 쉽지 않을것같다 가장 긴 트리의 지름과, 두번째로 긴 트리의 지름이 아예 관계 없는 곳에 있을 수도 있지 않을까? 아닌가? 트리의 지름과 두번째 트리의 지름이 끝 정점을 공유하지 않는다고 하자. 그렇다면, 위 그림과 같이 압축해서 나타낼 수 있다. 이 때, $a + b = D_1 \geq c + d = D_2$라 하자. 일반성을 잃지 않고 $a \geq b, c \geq d$라 하자. 서로 공유하는 정점 하나가 있는 경우 $a + c \geq D_1/2 + D_2/2 \geq D_2$ 이므로, a와 c를 지나는 경로가 우리가 가정한 두번째 지름보다 더 크거나 같다. 더 큰 경우 모순이고 같은 경우 $a+c$를 두번째 지름으로 택해도 아무 문제가 없다. 서로 공유하는 정점이 없는경우 (다른 서브트리에 나타낼 수 있는 경우) $a + c + e + f \geq D_1/2 + D_2/2 + e + f > D_2$ 이므로, $D_2$의 경로는 두번째 트리의 지름이 아니다. 따라서, 트리의 두번째 지름의 한 끝점은 트리의 지름의 한 끝점과 같다. DFS를 돌려서 트리의 지름 양 끝 점을 찾고, 거기서부터 두번째지름을 한번씩 찾아주자. 💻 풀이 # 코드 (C++): vector<pii> dfs(int cur, int par){ vector<pii> v; v.push_back({0, cur}); for(auto [nxt, w]: links[cur]){ if(nxt == par) continue; auto nv = dfs(nxt, cur); rep(i, 0, min(2, (int)nv.size())){ v.push_back({nv[i].first + w, nv[i].second}); } sort(all(v), greater<pii>()); while(v.size() > 2) v.pop_back(); } return v; } void solve(){ cin >> N; rep(i, 0, N-1){ int u, v, w; cin >> u >> v >> w; links[u].push_back({v, w}); links[v].push_back({u, w}); } int L = dfs(1, -1)[0].second; // 트리의 지름의 한쪽 끝 int ans = 0; auto ret = dfs(L, -1); ans = max(ans, ret[1].first); // 두번째 트리의 지름 후보 1 int R = ret[0].second; // 트리의 지름의 다른쪽 끝 ret = dfs(R, -1); ans = max(ans, ret[1].first); // 두번째 트리의 지름 후보 2 cout << ans << "\n"; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/5639 🧐 관찰 및 접근 # 이진 검색 트리의 전위 순회 결과를 이용해서 후위 순회 결과를 찾아내자! 트리가 만들어져 있다면, 후위 순회를 하는건 쉬울텐데… 전위 순회는 (루트 - 왼쪽서브트리 - 오른쪽서브트리)를 방문한다. 왼쪽 서브트리의 값은 언제나 루트보다 작고, 오른쪽 서브트리의 값은 언제나 루트보다 크므로 50 (루트) --- 30 (왼쪽 서브트리) 24 5 28 45 --- 98 (오른쪽 서브트리) 52 60 첫 입력에 대해, 이렇게 생각할 수 있지 않을까? 그리고 각 서브트리 또한 이진 검색트리이므로, 이를 재귀적으로 수행할 수 있다. 예를 들어, 왼쪽 서브트리에 대해서 30 (루트) --- 24 (왼쪽 서브트리) 5 28 --- 45 (오른쪽 서브트리) 위와 같이 말이다! 그렇다면, 재귀를 이용해서 트리를 구축하고 후위순회만 하면 끝난다. 💻 풀이 # 코드 (C++): vector<int> v; struct Node{ int val = -1; Node* left = nullptr; Node* right = nullptr; Node(int s, int e){ val = v[s]; if(s == e) return; int idx = e+1; rep(i, s+1, e+1){ if(v[i] > val){ idx = i; break; } } if(s+1 <= idx-1) left = new Node(s+1, idx-1); if(idx <= e) right = new Node(idx, e); } }; void postorder(Node* node){ if(node == nullptr) return; postorder(node->left); postorder(node->right); cout << node->val << '\n'; } void solve(){ int x; while(cin >> x) v.push_back(x); Node* root = new Node(0, v.size()-1); postorder(root); } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/5214 🧐 관찰 및 접근 # 나이브하게 생각해볼까? 인접 리스트로 간선을 저장한다고 생각하면, $M\binom{K}{2} \approx MK^2$ 개의 정보가 저장된다. 그러면 BFS의 시간복잡도는 $O(V+E)$ 니까 조금 곤란한데… 잘 생각해보면, (1, 2, 3, 4), (2, 3, 4, 5) 하이퍼튜브가 있다고 가정하면, 겹치는 정보가 너무나도 많다! 첫 하이퍼튜브를 타고 2, 3, 4번 역에 1회만에 도착했다면, 두번째 하이퍼튜브에서 2, 3, 4번이 서로를 움직일 필요가 없다. 하이퍼튜브는 최대 1000개 존재한다. 또한 한 역은 최대 1000개의 하이퍼튜브에 속한다. 하이퍼튜브만 따로 정리해서, 그 안에서 움직이면 되지 않을까? 💻 풀이 # 코드 (C++): void solve(){ cin >> N >> K >> M; rep(i, 0, M){ rep(j, 0, K){ int x; cin >> x; inhyper[x].push_back(i); hypertube[i].push_back(x); } } rep(i, 1, N+1) dist[i] = -1; dist[1] = 1; queue<int> q; q.push(1); while(!q.empty()){ int cur = q.front(); q.pop(); if(cur == N) break; for(int htube : inhyper[cur]){ for(int nxt : hypertube[htube]){ if(dist[nxt] == -1){ dist[nxt] = dist[cur] + 1; q.push(nxt); } } hypertube[htube].clear(); // 이미 방문한 하이퍼튜브는 볼일이 없다 } } cout << dist[N] << '\n'; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/2263 🧐 관찰 및 접근 # 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하자. 인오더: (왼쪽 -> 루트 -> 오른쪽) 포스트오더: (왼쪽 -> 오른쪽 -> 루트) 프리오더: (루트 -> 왼쪽 -> 오른쪽) 그렇다면, 어떤 한 서브트리에 대해, 포스트오더를 이용해서 루트를 찾을 수 있다. (맨 마지막 값) 그리고 이를 기점으로 인오더에서 왼쪽에 있는 모든 수는 왼쪽 서브트리, 나머지는 오른쪽 서브트리에 있다고 생각할 수 있다. 한 서브트리에서 루트노드의 값을 알아냈을 때, 인오더에서의 그 인덱스를 빠르게 찾을 수 있다면 왼쪽/오른쪽 서브트리로의 분할이 용이하다! map을 이용하면 $O(NlogN)$에 해결할 수 있겠다. 💻 풀이 # 코드 (C++): int N; vector<int> inorder, postorder; map<int, int> in_idx; void preorder(int in_s, int in_e, int post_s, int post_e){ if(in_s > in_e) return; int root = postorder[post_e]; cout << root << ' '; int idx = in_idx[root]; int sz = idx - in_s; preorder(in_s, idx-1, post_s, post_s + sz - 1); // 왼쪽 서브트리 preorder(idx+1, in_e, post_s + sz, post_e - 1); // 오른쪽 서브트리 } void solve(){ cin >> N; inorder.resize(N); postorder.resize(N); rep(i, 0, N) cin >> inorder[i]; rep(i, 0, N) cin >> postorder[i]; rep(i, 0, N) in_idx[inorder[i]] = i; preorder(0, N-1, 0, N-1); } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/1154 🧐 관찰 및 접근 # A / B팀으로 나누는걸 보면 당연히 이분그래프를 떠올릴 수 있겠는데.. 같은 그룹의 학생들끼리는 모두 서로 아는 사이여야 한다? 우리가 아는 이분그래프의 정의랑 뭔가 느낌이 다르다! 저 말을 다시한번 생각해보자 같은 그룹의 학생이다 -> 서로 아는사이이다 이 문장의 대우명제는? 서로 모르는 사이이다 -> 다른 그룹의 학생이다 그렇다면, 그래프의 간선을 뒤집어버리자! $N$은 최대 1000이므로, 간선 $M = N^2$개는 충분히 계산할 수 있다. 이렇게 간선을 뒤집은 그래프를 여 그래프, 혹은 complement graph라고 한다. 💻 풀이 # 코드 (C++): void solve(){ cin >> N; while(1){ int u, v; cin >> u >> v; if(u == -1 && v == -1) break; know[u][v] = know[v][u] = true; } bool isBipartite = true; vector<int> color(N+1, 0); rep(i, 1, N+1) if(color[i] == 0){ queue<int> Q; Q.push(i); color[i] = 1; while(!Q.empty()){ int cur = Q.front(); Q.pop(); rep(nxt, 1, N+1){ if(cur == nxt) continue; if(know[cur][nxt]) continue; if(color[nxt] == 0){ color[nxt] = (color[cur] == 1 ? 2 : 1); Q.push(nxt); } else if(color[nxt] == color[cur]){ isBipartite = false; break; } } } } if(!isBipartite){ cout << -1; return; } vector<int> team1, team2; rep(i, 1, N+1){ if(color[i] == 1) team1.push_back(i); else team2.push_back(i); } cout << 1 << "\n"; for(auto x: team1) cout << x << " "; cout << -1 << "\n"; for(auto x: team2) cout << x << " "; cout << -1 << "\n"; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/34830 🧐 관찰 및 접근 # 문제 상황을 차근차근 살펴보자 $a, b$가 있을 때, $a - b$ 를 한번 지나가면 된다. $a, b, c$가 있을 때, $a - b, b- c, c-a$를 한번씩 지나가야한다. $a, b,c ,d$가 있을 때, $a-b, a-c, a-d, b-c, b-d, c-d$를 한번씩 지나가야 한다. 이를 그래프 이론으로 해석할 수 있지 않을까? 그래프가 있고, 각 간선을 한번씩 지나되, 시점과 종점이 달라도 된다 한붓그리기가 가능한가? 이제 이 문제는 오일러 경로를 가능하게 하는 문제로 바뀐다. 오일러 경로는, 홀수점이 두개 이하일때 가능하다. 정점이 $N$개 있다고 하면, 그래프는 완전그래프이므로 각 정점에 붙어있는 간선은 $N-1$개이다. $N$이 홀수라면, 모든 $N$개의 정점은 짝수점이다. $N$이 짝수라면, 모든 $N$개의 정점은 홀수점이다. 따라서, $N-2$개의 점들을 연결해서 홀수점이 2개가 되도록 만드는것이 최적이다. 💻 풀이 # 코드 (C++): void solve(){ ll N; cin >> N; ll ans = N * (N-1) / 2; if(N%2 == 0) ans += N/2 - 1; cout << ans; }

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/23086 🧐 관찰 및 접근 # 그래프와 간선이 주어졌을때, 특정 시점에 이분 그래프인가?를 찾는 문제이다. 이분그래프를 판정하는데에는 $O(N+M)$의 시간이 걸린다. 직관적으로 생각해보면, 리스트에 쓰인 차례대로 친한 친구를 절교시킬 수 있으므로, 리스트를 뒤집어서 하나씩 간선을 이어가며 해당 그래프가 이분 그래프인지 판정하는 방법을 쓸 수 있을 것이다. 이때 시간 복잡도는 $O(K(N+M))$이다. 이는 너무 느리다! 문제 상황을 조금 더 관찰해보자. $\text{ans}$개의 친한 친구 쌍을 절교시켜 이분 그래프가 성립하도록 했다면, $\text{ans}+1$개의 쌍을 절교시켰을때도 마찬가지로 이분그래프일 것이다. $0 \leq a \leq K$인 $a$에 대해, 이분그래프가 성립하는지는 단조성이 존재한다! **매개변수 탐색(파라메트릭 서치)**가 가능하다. 💻 풀이 # 코드 (C++): int N, M, K; vector<pair<int, int>> links[100010]; // (nxt, idx) vector<int> prohibit_list; int color[100010]; // 0: unvisited, 1: group A, 2: group B bool prohibited[200010]; bool isBipartite(int cnt){ rep(i, 1, M+1) prohibited[i] = false; rep(i, 0, cnt) prohibited[prohibit_list[i]] = true; rep(i, 1, N+1) color[i] = 0; rep(i, 1, N+1) if(color[i] == 0){ queue<int> Q; Q.push(i); color[i] = 1; while(!Q.empty()){ int cur = Q.front(); Q.pop(); for(auto [nxt, idx]: links[cur]){ if(prohibited[idx]) continue; if(color[nxt] == 0){ color[nxt] = (color[cur] == 1 ? 2 : 1); Q.push(nxt); } else if(color[nxt] == color[cur]){ return false; } } } } return true; } void solve(){ cin >> N >> M >> K; rep(i, 1, M+1){ int u, v; cin >> u >> v; links[u].push_back({v, i}); links[v].push_back({u, i}); } rep(i, 0, K){ int p; cin >> p; prohibit_list.push_back(p); } // 모두 금지했을때 이분 그래프인가? if(!isBipartite(K)){ cout << -1; return; } // 파라메트릭 서치 int ok = K, ng = -1; while(ok - ng > 1){ int mid = (ok + ng) >> 1; if(isBipartite(mid)) ok = mid; else ng = mid; } cout << ok << "\n"; int groupA_sz = 0, groupB_sz = 0; isBipartite(ok); rep(i, 1, N+1) color[i] == 1 ? groupA_sz++ : groupB_sz++; cout << min(groupA_sz, groupB_sz) << ' ' << max(groupA_sz, groupB_sz) << "\n"; } 🔒 구현 코드 잠금