Algorithm

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/1734 🧐 관찰 및 접근 # 무향 그래프 $G = (V, E)$가 주어진다. 여기서 두가지 쿼리가 주어진다. 간선 $e \in E$ 하나를 없앴을 때, 정점 $A, B$의 연결성 판정 정점 $v \in V$ 하나를 없앴을 때, 정점 $A, B$의 연결성 판정 각각 살펴보자. 먼저, 문제조건에 의해 컴포넌트는 하나이므로 A, B는 기본적으로 연결되어있다고 판단하자.

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/1647 🧐 관찰 및 접근 # 집 (정점)과 길 (간선)이 있다. 마을 두개로 분리해야한다. 이 때, 간선의 가중치의 합을 최소화해야한다. 이미 두 집이 한 마을 안에 있다면, 둘이 연결할 필요가 없다. 이미 다른 우회로로 갈 수 있기 때문 연결하던 도중 마을이 두개가 남았다면 끝내면 된다. 크루스칼 알고리즘으로 덩어리가 두개가 남을때까지 반복하면 되겠다. 💻 풀이 # 코드 (C++): void solve(){ int N, M; cin >> N >> M; vector<tuple<int, int, int>> edges; // weight, u, v rep(i, 0, M){ int u, v, w; cin >> u >> v >> w; edges.emplace_back(w, u, v); } UF.init(N+1); sort(all(edges)); int ans = 0; for(auto &[w, u, v]: edges){ if(UF.group == 3) break; if(UF.merge(u, v)) ans += w; } cout << ans << "\n"; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/10775 🧐 관찰 및 접근 # 1번 게이트가 제일 쓰기 좋아보인다. 그러므로 1번 게이트를 아낀다고 생각하면, 모든 비행기를 도킹시킬때 갈 수 있는 최댓값으로 도킹시키면 되는 것 같다. 이를 나이브하게 구현하면 한번당 $O(G)$가 걸릴 것이다. 100000 100000 100000 100000 100000 ... 과 같은 테스트케이스를 생각해보면 된다. 따라서 $\text{calc}(g_i) = g_i$ 보다 작거나 같은 살아있는 게이트의 최댓값을 빠르게 찾으면 된다. 이는 유니온파인드로 빠르게 수행 가능하다! merge할때 자신보다 작은 값을 가리키게 하자. 💻 풀이 # 코드 (C++): void solve(){ int G, P; cin >> G >> P; UF.init(G+1); int ans = 0; while(P--){ int g; cin >> g; int rt = UF.find(g); if(rt == 0) break; UF.merge(rt, rt-1); ans++; } cout << ans << "\n"; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/1043 🧐 관찰 및 접근 # 지민이는 모든 파티에 참여해야하므로, 진실을 아는 사람이 있는 파티의 모든 사람은 진실을 알게 된다. 모든 파티에 대해 진실을 알게 된 사람을 확인한 후, 진실을 아는사람이 없는 파티들의 수를 세면 된다. 유니온 파인드, 분리 집합으로 해결하자. 💻 풀이 # 코드 (C++): void solve(){ int N, M; cin >> N >> M; vector<vector<int>> parties; UnionFind UF(N+1); // 0은 진실을 아는 사람 int cnt; cin >> cnt; rep(i, 0, cnt){ int a; cin >> a; UF.merge(0, a); } rep(i, 0, M){ cin >> cnt; vector<int> party(cnt); rep(j, 0, cnt) cin >> party[j]; parties.push_back(party); rep(j, 0, cnt-1) UF.merge(party[j], party[j+1]); } int ans = 0; for(auto party: parties){ bool flag = true; for(auto p: party) if(UF.find(p) == 0) flag = false; if(flag) ans++; } cout << ans; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/4013 🧐 관찰 및 접근 # 그래프가 DAG라면 위상정렬을 하면서 DP를 진행할 수 있을텐데.. 같은 정점을 여러번 들릴 수 있으므로, 어떤 정점이 사이클 안에 들어있다면 해당 사이클 내의 ATM을 모두 들릴 수 있다! 서로 자유롭게 이동 가능한 관계라면 모두 자유롭게 들릴 수 있으므로, 이를 SCC로 묶어 DAG로 만들자. 💻 풀이 # 코드 (C++): void solve(){ cin >> N >> M; DirectedGraph graph(N+1); rep(i, 0, M){ int u, v; cin >> u >> v; graph.add_edge(u, v); } DirectedGraph dag = graph.getCompressedGraph(); int sz = dag.V; vector<int> val(sz), DP(sz, -1e9), indeg(sz, 0); rep(i, 1, N+1){ int X; cin >> X; val[graph.sccId[i]] += X; } int S, P; cin >> S >> P; S = graph.sccId[S]; DP[S] = val[S]; rep(u, 0, sz) for(auto &v: dag.links[u]) indeg[v]++; queue<int> Q; rep(i, 0, sz) if(indeg[i] == 0) Q.push(i); while(!Q.empty()){ int cur = Q.front(); Q.pop(); for(auto nxt: dag.links[cur]){ DP[nxt] = max(DP[nxt], DP[cur] + val[nxt]); indeg[nxt]--; if(indeg[nxt] == 0) Q.push(nxt); } } int ans = 0; rep(i, 0, P){ int X; cin >> X; X = graph.sccId[X]; ans = max(ans, DP[X]); } cout << ans << '\n'; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/3648 🧐 관찰 및 접근 # 모든 심사위원에 대해 (and) 각 심사위원별로 표 두개중 하나를 만족해야 한다. (or) 따라서 $(A \lor B) \land (C \lor D) \land \cdots$ 의 2-sat 문제로 변환 가능하다! 모델링만 잘 해보자. 가능한 변수의 개수 $= 1000 *2 = 2000$ 에 대해 $i$ 번 참가자가 진출: $2*i$, 진출 실패: $2*i+1$로 모델링하자. 1번 참가자인 상근이는 무조건 통과해야 한다. $\neg x \to x$ 를 만족하면 되므로, $1 \to 0$을 추가하자. 💻 풀이 # 코드 (C++): void solve(){ int N, M; while(cin >> N >> M){ DirectedGraph dg(2*N); rep(i, 0, M){ int u, v; cin >> u >> v; if(u > 0) u = 2*(u-1); else u = 2*(-u-1)+1; if(v > 0) v = 2*(v-1); else v = 2*(-v-1)+1; dg.add_2sat_edge(u, v); } dg.add_2sat_edge(0, 0); cout << (dg.is2SAT() ? "yes\n" : "no\n"); } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/3176 🧐 관찰 및 접근 # 도로가 N-1개인걸 보니 트리겠구만 이때 경로상에서 가장 짧은 도로의 길이와 가장 긴 도로의 길이를 출력하라는데… HLD를 써도 되지만, sparse table에서의 RMQ처리처럼 진행해도 큰 문제가 없겠다. 💻 풀이 # 코드 (C++): 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}); } dfs(1, -1, 0); rep(j, 1, 20) rep(i, 1, N+1) if(par[i][j-1]){ par[i][j] = par[par[i][j-1]][j-1]; mnDist[i][j] = min(mnDist[i][j-1], mnDist[par[i][j-1]][j-1]); mxDist[i][j] = max(mxDist[i][j-1], mxDist[par[i][j-1]][j-1]); } int Q; cin >> Q; while(Q--){ int u, v; cin >> u >> v; auto [mn, mx] = calc(u, v); cout << mn << ' ' << mx << '\n'; } } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/1761 🧐 관찰 및 접근 # 트리에서, 두 정점 사이의 경로는 유일하다. 해당 경로는 두 정점의 LCA를 지난다. 두 점 사이의 거리는 $d(u) + d(v) - 2*d(\text{LCA}(u, v))$로 계산할 수 있다. 💻 풀이 # 코드 (C++): void dfs(int cur, int _par){ for(auto [nxt, w]: links[cur]){ if(nxt == _par) continue; dist[nxt] = dist[cur] + w; depth[nxt] = depth[cur] + 1; par[nxt][0] = cur; dfs(nxt, cur); } } int LCA(int u, int v){ if(u == v) return u; if(depth[u] < depth[v]) swap(u, v); int diff = depth[u] - depth[v]; rep(i, 0, 16) if((diff >> i) & 1) u = par[u][i]; if(u == v) return u; rrep(i, 16, 0){ if(par[u][i] != par[v][i]){ u = par[u][i]; v = par[v][i]; } } return par[u][0]; } ll getDist(int u, int v){ int lca = LCA(u, v); return dist[u] + dist[v] - 2 * dist[lca]; } 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}); } dfs(1, -1); rep(j, 1, 16) rep(i, 1, N+1) par[i][j] = par[par[i][j-1]][j-1]; cin >> Q; while(Q--){ int u, v; cin >> u >> v; cout << getDist(u, v) << '\n'; } } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/16367 번역 문제 번역 # Mr. Dajuda는 TV 쇼 프로그램으로 유명한 사람으로, 가끔 시청자들에게 흥미로운 게임을 제안하고 상품을 상으로 제공합니다. 이번 주에 그가 제안한 게임은 다음과 같이 설명할 수 있습니다. 무대 위의 k개(k > 3)의 램프는 게임 시작 시 모두 꺼져 있습니다. 편의상 램프는 1부터 k까지 번호가 매겨져 있습니다. 각 램프는 빨간색 또는 파란색의 색상을 가지고 있습니다. 그러나 램프의 색상은 켜지기 전까지는 알 수 없습니다. 게임 참가자들은 무작위로 세 개의 램프를 선택하고 그 색상을 예측하도록 요청받습니다. 그런 다음 각 참가자는 선택한 램프의 예측된 색상이 기록된 종이를 게임 진행자인 Mr. Dajuda에게 제출합니다. 모든 램프가 켜지면 각 참가자는 자신이 예측한 색상 중 몇 개가 램프의 실제 색상과 일치하는지 확인합니다. 두 개 이상의 색상이 일치하면 상품을 받게 됩니다.

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/14908 🧐 관찰 및 접근 # 직관적으로 생각해보자 어떤 작업의 보상금 $S_i$가 크다면, 빠르게 작업을 수행하는게 좋다. 어떤 작업을 완료하는데 걸리는 시간 $T_i$가 작다면, 빠르게 작업을 수행하는게 좋다. 이 두가지를 어떻게 동시에 활용할 수 있을까? 어떤 정답 $Opt$가 존재한다고 가정해보자. 이때, $Opt$의 순서중 가운데 두 작업 $W_i, W_{i+1}$을 바꾼다고 해보자. 이 때, 바뀐 순서 $Opt'$가 $Opt$보다 나을 수 있을까? 두 작업을 바꾸면, $Opt' = Opt + S_i * T_{i+1} - S_{i+1} * T_i$가 된다. 다시말해, $S_i * T_{i+1} - S_{i+1} * T_i$ 이 음수라면 더 나은 해법을 찾을 수 있다. 따라서 $S_i * T_{i+1} - S_{i+1} * T_i > 0$인 방향, 즉 $\frac{S_i}{T_i} \geq \frac{S_{i+1}}{T_{i+1}}$ 의 순서로 정렬하면 최적해가 된다. 💻 풀이 # 코드 (C++): void solve(){ int N; cin >> N; vector<array<int, 3>> ans; // S, T, idx; rep(i, 0, N){ int S, T; cin >> S >> T; ans.push_back({T, S, i+1}); } sort(all(ans), [](const array<int, 3> &a, const array<int, 3> &b){ if(a[0]*b[1] == a[1]*b[0]) return a[2] < b[2]; return a[0]*b[1] > a[1]*b[0]; }); for(auto &p: ans) cout << p[2] << ' '; } 🔒 구현 코드 잠금