Algorithm

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/30449 🧐 관찰 및 접근 # $R(n)$의 길이는 몇일까? $R(1) = 2$이고, $R(k) = R(k-1) + k$와 서로소인 자연수의 개수 인 것 같다. 오일러 피함수의 부분합 개수랑 같다. 암튼 나이브하게 돌려보니, 7600459개가 나온다. 이걸 0.5초안에 이걸 정렬하고 찾을?수?있을까? ㅋㅋ 수열이 좌우로 대칭인걸 고려하면 380만개정도만 정렬해도 될거같긴 한데… 그래도 빡세보인다. 0.5초라서 흠.. 답에 대한 이분탐색이 될까? 사실 깔끔하게 이분탐색 하기 위해선, 정수조건으로 바꾸려면 1~5000의 LCM을 구해야 한다.. 진짜 개에바 $10^{-4}$에 대한 정밀도까지만 하면 되지 않을까? 해봤자 가장 작은 수는 $\frac{1}{5000}$이니까… 라기엔 두 분수의 차는 결국 더 빡세지네. 해봤자 $\frac{1}{5000*4999}$인거같긴 한데… 아니 잠깐만, 생각해보니까 1~5000에 대해서 따로 정렬하면 시간복잡도가 꽤나 줄어드는것같다. 이렇게 해서 답에 대한 이분탐색을 해볼까..? 다 실패하고, nth_element와 short와 pragma Ofast와 Clang까지 섞은 최적화로 풀엇다… 하 이게 뭐하는 문제냐 ㄱ- 헉, 앞에 최대공약수를 구하는 부분을 반복문으로 전처리하면 훨씬 빠르게 돈다. 거기가 병목이었다니 💻 풀이 # 코드 (C++): void solve(){ int N, K; cin >> N >> K; vector<pair<short,short>> v; v.reserve(N * N / 2); v.push_back({0, 1}); v.push_back({1, 1}); rep(i, 1, N+1) rep(j, i+1, N+1){ if(__gcd(i, j) != 1) continue; v.push_back({(short)i, (short)j}); } int sz = (int)v.size(); if(K*2 > sz){ K = sz - K + 1; nth_element(v.begin(), v.begin() + K - 1, v.end(), [](auto& a, auto& b){ return a.first * b.second > a.second * b.first; }); } else { nth_element(v.begin(), v.begin() + K - 1, v.end(), [](auto& a, auto& b){ return a.first * b.second < a.second * b.first; }); } cout << v[K-1].first << " " << v[K-1].second << '\n'; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/4817 🧐 관찰 및 접근 # 최대한 괄호를 제거해야 한다. 괄호 안에 덧셈이 없다면, 해당 괄호는 제거해도 된다. 어떨 때 괄호를 살려야 하는가? $((x+y)z)$와 같이, 어떤 괄호로 이루어진 덧셈이 포함된 식과 어떤 식이 곱해지는 경우 남겨야 한다. 라곤 했지만… 구현이 만만치 않다. 이를 위해 추상 구문 트리 라는것을 보통 사용한다고 한다. 노드단위로 연산을 나타내자. 이때 파싱 과정에서, 연산 우선순위가 낮은걸 먼저 해야한다. (상위 노드가 먼저 계산되므로) 따라서 덧셈 -> 곱셈 -> 괄호의 순서로 진행하자. 쉽지 않은데.. 이런 생각보다 파서를 만드는 과정이 재밌다. 전산언어학 문제를 좀더 풀어보도록 하자. 💻 풀이 # 코드 (C++): struct Node{ char type; char var; Node *left, *right; Node(char c){ // var type = 'v'; var = c; left = right = nullptr; } Node(char op, Node *l, Node *r){ // op type = 'o'; var = op; left = l; right = r; } }; struct AST{ Node *root; AST(Node *r) : root(r) {} string emit(Node *n, char parOp){ if(n->type == 'v') return string(1, n->var); if(n->var == '+'){ string L = emit(n->left, '+'); string R = emit(n->right, '+'); if(parOp == '*') return "(" + L + "+" + R + ")"; return L + "+" + R; } return emit(n->left, '*') + emit(n->right, '*'); } string toString(){ return emit(root, 0); } }; struct Parser{ const string &S; int pos; Parser(const string &s): S(s), pos(0){} Node *parseVal(){ if(S[pos] == '('){ pos++; Node *node = parsePlus(); pos++; return node; } return new Node(S[pos++]); } Node *parseMul(){ Node *node = parseVal(); while(pos < (int)S.size() && (islower(S[pos]) || S[pos] == '(')){ Node *right = parseVal(); node = new Node('*', node, right); } return node; } Node *parsePlus(){ Node *node = parseMul(); while(pos < (int)S.size() && S[pos] == '+'){ pos++; Node *right = parseMul(); node = new Node('+', node, right); } return node; } AST parse(){ return AST(parsePlus()); } }; void solve(){ string S; while(cin >> S){ Parser parser(S); AST ast = parser.parse(); cout << ast.toString() << "\n"; } } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/17435 🧐 관찰 및 접근 # 함수 $f$가 주어질 때, 최대 $500\,000$번 합성한 값을 구해야 한다. 나이브하게 계산하면 $O(QN)$으로 시간초과다. 전체를 전처리해두기엔, 공간복잡도가 $O(mN)$으로 너무 커진다. 따라서 적당히 전처리를 해두자. 이는 LCA에서 했던것과 같이, 희소 배열로 가능할 것 같다. 각 정의역에 대해 $1$번, $2$번, $4$번, $\cdots 2^k$번 합성한 결과를 저장해서 쿼리를 처리하자. 💻 풀이 # 코드 (C++): void solve(){ int N; cin >> N; vector<vector<int>> f(20, vector<int>(N+1)); rep(i, 1, N+1) cin >> f[0][i]; rep(k, 1, 20) rep(i, 1, N+1) f[k][i] = f[k-1][f[k-1][i]]; int Q; cin >> Q; while(Q--){ int n, x; cin >> n >> x; rep(k, 0, 20) if(n & (1 << k)) x = f[k][x]; cout << x << "\n"; } } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/7562 🧐 관찰 및 접근 # 가중치가 없으니, 간단한 BFS로 풀릴 것 같다. 시간복잡도는 $O(V + E) \approx O(N^2)$이다. 💻 풀이 # 코드 (C++): void solve(){ int dx[8] = {-2, -2, -1, -1, 1, 1, 2, 2}; int dy[8] = {-1, 1, -2, 2, -2, 2, -1, 1}; int N; cin >> N; vector<vector<int>> board(N, vector<int>(N, -1)); int sx, sy, ex, ey; cin >> sx >> sy >> ex >> ey; queue<pii> q; q.push({sx, sy}); board[sx][sy] = 0; while(!q.empty()){ auto [cx, cy] = q.front(); q.pop(); if(cx == ex && cy == ey){ cout << board[cx][cy] << "\n"; return; } rep(d, 0, 8){ int nx = cx + dx[d]; int ny = cy + dy[d]; if(nx < 0 || nx >= N || ny < 0 || ny >= N) continue; if(board[nx][ny] == -1){ board[nx][ny] = board[cx][cy] + 1; q.push({nx, ny}); } } } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/5925 🧐 관찰 및 접근 # X로 그려지는 영역이 3개가 있고, 최소한의 비용으로 이들을 연결해야한다. 멀티 소스 BFS와 같은 맛으로 가능할 것 같다. 3개니까 전수조사 해도 되겠지. 아, 근데 좀 사고인 경우가 있구나. ..... ..X.. .X.X. ..... 위와 같은 경우에, 하나만으로도 칠할 수 있는 것 같다. 위와 같은 경우에, 세 그룹이 한 정점에서 무조건 모이게 된다. 따라서 빈 정점을 잡고, 거기서 세 그룹까지의 최단경로를 이용하자. 💻 풀이 # 코드 (C++): void solve(){ int N, M; cin >> N >> M; vector<string> S(N); rep(i, 0, N) cin >> S[i]; vector<vector<int>> board(N, vector<int>(M)); int color = 0; rep(i, 0, N) rep(j, 0, M) { if(S[i][j] == 'X' && board[i][j] == 0){ queue<pii> Q; Q.push({i, j}); board[i][j] = ++color; while(!Q.empty()){ auto [cx, cy] = Q.front(); Q.pop(); rep(d, 0, 4){ int nx = cx + dx[d]; int ny = cy + dy[d]; if(nx < 0 || nx >= N || ny < 0 || ny >= M) continue; if(S[nx][ny] == 'X' && board[nx][ny] == 0){ board[nx][ny] = color; Q.push({nx, ny}); } } } } } vector<ll> dists; auto getDist = [&](int c1, int c2) -> ll { vector<vector<int>> dist(N, vector<int>(M, -1)); queue<pii> Q; rep(i, 0, N) rep(j, 0, M){ if(board[i][j] == c1){ dist[i][j] = 0; Q.push({i, j}); } } while(!Q.empty()){ auto [cx, cy] = Q.front(); Q.pop(); rep(d, 0, 4){ int nx = cx + dx[d]; int ny = cy + dy[d]; if(nx < 0 || nx >= N || ny < 0 || ny >= M) continue; if(board[nx][ny] == c2){ return dist[cx][cy]; } if(board[nx][ny] == 0 && dist[nx][ny] == -1){ dist[nx][ny] = dist[cx][cy] + 1; Q.push({nx, ny}); } } } return (ll)1e18; }; rep(i, 1, 4) rep(j, i+1, 4) dists.push_back(getDist(i, j)); sort(all(dists)); ll ans = dists[0] + dists[1]; auto getDist2 = [&](int cx, int cy, int c) -> ll { vector<vector<int>> dist(N, vector<int>(M, -1)); queue<pii> Q; dist[cx][cy] = 0; Q.push({cx, cy}); while(!Q.empty()){ auto [x, y] = Q.front(); Q.pop(); rep(d, 0, 4){ int nx = x + dx[d]; int ny = y + dy[d]; if(nx < 0 || nx >= N || ny < 0 || ny >= M) continue; if(board[nx][ny] == c){ return dist[x][y]; } if(board[nx][ny] == 0 && dist[nx][ny] == -1){ dist[nx][ny] = dist[x][y] + 1; Q.push({nx, ny}); } } } return (ll)1e18; }; rep(i, 0, N) rep(j, 0, M) if(board[i][j] == 0){ ans = min(ans, getDist2(i, j, 1) + getDist2(i, j, 2) + getDist2(i, j, 3) + 1); } cout << ans << "\n"; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/33527 🧐 관찰 및 접근 # 뭔가 전반적으로 세팅이 BOJ 5214 환승이 생각나는 것 같기도? 나이브하게 돈다면, 각 노선에 있을 수 있는 최대 정류장 수가 10만개니까, 이걸 다 돌기 시작하면 상당히 막막해진다. 그림을 그려서 어떤 상황인지 더 잘 판단해보자. ![[Drawing 2026-02-17 14.06.51.excalidraw.png]] 일단 예제 1번은 이런데, 흠. 확실히 정류장보단 노선 단위로 어떻게 잘 보고싶긴 하다. 노선은 총 $5 \times X = 500$개이다. 이때, 노선의 환승 각 정류장 $N$개마다 $\binom{5}{2}$ 개이므로 최대 $100\,000 \times = 1\,000\,000$개인 것 같다. 중복도 제거할수도 있고. 아? 이게 노선이 충분히 적으니, 플로이드 워셜이 가능해보인다. 쿼리는 정점에 대해 들어오니, $U_i, V_i$가 각각 5개 노선에 속하는 경우 25가지에 대해 노선으로 계산하면 될 것 같다. 💻 풀이 # 코드 (C++): void solve(){ int N, X; cin >> N >> X; vector<array<int, 5>> bus(N); rep(i, 0, N) rep(j, 0, 5) cin >> bus[i][j]; auto toIdx = [&](pii p){ return p.first*X + (p.second - 1); }; vector<vector<int>> dist(5*X, vector<int>(5*X, 1e9)); rep(i, 0, 5*X) dist[i][i] = 0; rep(i, 0, N) rep(j, 0, 5) rep(k, j+1, 5){ int u = toIdx({j, bus[i][j]}), v = toIdx({k, bus[i][k]}); dist[u][v] = dist[v][u] = 1; } rep(k, 0, 5*X) rep(i, 0, 5*X) rep(j, 0, 5*X) dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); int Q; cin >> Q; while(Q--){ int u, v; cin >> u >> v; int ans = 1e9; rep(i, 0, 5) rep(j, 0, 5){ int idx_u = toIdx({i, bus[u-1][i]}), idx_v = toIdx({j, bus[v-1][j]}); ans = min(ans, dist[idx_u][idx_v]); } cout << (ans == 1e9 ? -1 : ans+1) << "\n"; } } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/32655 🧐 관찰 및 접근 # 시작 정점에서 각 출구로 갈 수 있는 최단 경로를 구한 후, 열리는 타이밍에 맞춰 나갈 수 있는 최소 시간을 구하자. $KX$초 단위로 출구가 도는게 로테이션 돌고, 이분탐색으로 그 타이밍을 찾은 후 그 블럭에서 나갈 수 있는지, 그 다음블럭에서 나갈 수 있는지 체크하면 될 것 같다. 💻 풀이 # 코드 (C++): void solve(){ ll N, M, K; cin >> N >> M >> K; vector<vector<pll>> links(N+1); rep(i, 0, M){ ll u, v, w; cin >> u >> v >> w; links[u].push_back({v, w}); links[v].push_back({u, w}); } vector<ll> dist(N+1, LLONG_MAX); priority_queue<pll, vector<pll>, greater<pll>> pq; dist[1] = 0; pq.push({0, 1}); while(!pq.empty()){ auto [cd, cur] = pq.top(); pq.pop(); if(dist[cur] < cd) continue; for(auto [nxt, w]: links[cur]){ ll nd = cd + w; if(nd < dist[nxt]){ dist[nxt] = nd; pq.push({nd, nxt}); } } } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/23807 🧐 관찰 및 접근 # 무향그래프고, 정해진 정점중 세개 이상의 정점을 지나야 한다.. 이걸 경로로 나타내면 $X \rightarrow P_i \rightarrow P_j \rightarrow P_k \rightarrow Z$이 될 것이다. 이때, $X$에서 시작한 경로와 $Z$에서 시작한 최단 경로는 다익스트라로 쉽게 계산할 수 있다. 이제 가운데 $P_j$에서 시작한 최단 경로를 구해서, 각 $P_i, P_k$에 대해 구하면 되겠다. $O(V+E)$의 다익스트라를 $P \leq 100$번 돌려야 한다. 조금 무거운 4천만정도일거같은데, 6초제한이니 잘 돌것같다. 💻 풀이 # 코드 (C++): void solve(){ ll N, M; cin >> N >> M; vector<vector<pll>> links(N+1); rep(i, 0, M){ ll u, v, w; cin >> u >> v >> w; links[u].push_back({v, w}); links[v].push_back({u, w}); } int X, Z; cin >> X >> Z; vector<ll> dist_fromX(N+1, 1e18), dist_fromZ(N+1, 1e18); auto dijkstra = [&](ll start, vector<ll> &dist){ priority_queue<pll, vector<pll>, greater<pll>> pq; dist[start] = 0; pq.push({0, start}); while(!pq.empty()){ auto [cd, cur] = pq.top(); pq.pop(); if(cd > dist[cur]) continue; for(auto [nxt, w] : links[cur]){ ll nd = cd + w; if(nd < dist[nxt]){ dist[nxt] = nd; pq.push({nd, nxt}); } } } }; dijkstra(X, dist_fromX); dijkstra(Z, dist_fromZ); int P; cin >> P; vector<int> cand(P); rep(i, 0, P) cin >> cand[i]; ll ans = 1e18; for(int c2: cand){ vector<ll> dist_fromC(N+1, 1e18); dijkstra(c2, dist_fromC); for(int c1: cand) for(int c3: cand){ if(c1 == c2 || c2 == c3 || c1 == c3) continue; ans = min(ans, dist_fromX[c1] + dist_fromC[c1] + dist_fromC[c3] + dist_fromZ[c3]); } } if(ans >= 1e18) ans = -1; cout << ans; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/21940 🧐 관찰 및 접근 # 일단 가중치가 있는 방향 그래프인데.. 어떤 도시 $X$에 대해 준형이와 친구들이 살고있는 모든 도시에 대해 왕복 시간을 구할 수 있을까? $N$이 충분히 작으므로, 플로이드 워셜을 사용해서 모든 도시간의 이동시간을 구할 수 있겠다. 이후에는 모든 도시 $X$에 대해 $K$번의 계산으로 왕복시간들의 최댓값을 구할 수 있다. 시간복잡도 $O(N^3 + NK)$로 풀릴 것 같다! 💻 풀이 # 코드 (C++): void solve(){ cin >> N >> M; rep(i, 0, N) rep(j, 0, N) cost[i][j] = 1e15; rep(i, 0, N) cost[i][i] = 0; rep(i, 0, M){ int u, v, w; cin >> u >> v >> w; u--; v--; cost[u][v] = w; } rep(k, 0, N) rep(i, 0, N) rep(j, 0, N) cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j]); cin >> K; vector<int> v(K), ans; rep(i, 0, K) cin >> v[i]; ll mn = 1e15; rep(X, 0, N){ ll tmp = 0; for(auto c: v) tmp = max(tmp, cost[X][c-1] + cost[c-1][X]); if(tmp < mn){ mn = tmp; ans.clear(); } if(tmp == mn) ans.push_back(X+1); } for(auto c: ans) cout << c << ' '; } 🔒 구현 코드 잠금

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/1865 🧐 관찰 및 접근 # 무향인 도로와 유향인 웜홀이 있고, 음수 사이클이 있는지를 체크하는 문제이다. $N \leq 500$으로 크지 않으므로, 플로이드 워셜도 충분히 돈다. 이건 $O(N^3)$ 하지만 벨만포드로 $O(VE)$로 더 빠르게도 풀 수 있다. 벨만포드가 된다는건 SPFA로도 더 빠르게 풀 수 있다! 다 해본 결과, 플로이드워셜이 496ms, 벨만포드가 24ms, SPFA가 12ms가 나왔다. 💻 풀이 # 코드 (C++): void solve(){ int N, M, W; cin >> N >> M >> W; vector<vector<ll>> cost(N, vector<ll>(N, 1e15)); rep(i, 0, N) cost[i][i] = 0; rep(i, 0, M){ ll u, v, w; cin >> u >> v >> w; u--; v--; cost[u][v] = min(cost[u][v], w); cost[v][u] = min(cost[v][u], w); } rep(i, 0, W){ ll u, v, w; cin >> u >> v >> w; u--; v--; cost[u][v] = min(cost[u][v], -w); } rep(k, 0, N) rep(i, 0, N) rep(j, 0, N) cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j]); rep(i, 0, N) if(cost[i][i] < 0){ cout << "YES\n"; return; } cout << "NO\n"; } 🔒 구현 코드 잠금