hibye1217의 ALOHA & SHARC 탐방기 hibye1217의 ALOHA & SHARC 탐방기

1. [1753] 최단경로 (Gold V) 더보기 다익스트라를 그대로 구현해주면 됩니다. 지금까지 봐왔던 문제와는 달리 "방향그래프", 즉 간선이 \( v \rightarrow w \)임에 주의하세요. const ll INF = 0x3f3f3f3f3f3f3f3f; vector adj[20020]; priority_queue pq; ll dis[20020]; void Main(){ int n, m, st; cin >> n >> m >> st; while (m--){ int v, w, x; cin >> v >> w >> x; adj[v].push_back({w, x}); } memset(dis, 0x3f, sizeof(dis)); pq.push({0, st}); d..

1. [10845] 큐 (Silver IV) 더보기 STL 큐에 있는 6가지 연산들을 그대로 써주면 됩니다. 비어있을 때 -1을 출력하는 부분들만 잘 예외처리하면 됩니다. + STL queue에 back이 있다는 건 저도 풀이를 쓰면서 알았습니다. queue que; void Main(){ int q; cin >> q; while (q--){ string typ; cin >> typ; if (typ == "push"){ int x; cin >> x; que.push(x); } if (typ == "pop"){ if (que.empty()){ cout

+ 일부 문제에 대해 my3님의 기하 템플릿이 적용되었습니다. 미리 감사의 말씀을 드리고 시작하겠습니다. 1. [11758] CCW (Gold V) 더보기 문제에서 하라는대로 CCW를 구현해주면 됩니다. int ccw(pl2 a, pl2 b, pl2 c){ ll x = a.fr*b.sc + b.fr*c.sc + c.fr*a.sc; ll y = a.fr*c.sc + c.fr*b.sc + b.fr*a.sc; ll res = x-y; if (res > 0){ return 1; } if (res > a.fr >> a.sc >> b.fr >> b.sc >> c.fr >> c.sc; cout

1. [1260] DFS와 BFS (Silver II) 더보기 DFS와 BFS를 구현하는 문제입니다. 사전순으로 방문해야 하니, 인접 리스트 adj를 정렬해야 합니다. 시간복잡도는 \( O(V+E) \)가 됩니다. + 인접 행렬을 사용할 경우, DFS와 BFS의 시간복잡도가 \( O(V^2) \)이 됩니다. int n, m; vector adj[1020]; bool chk[1020]; void dfs(int now){ chk[now] = 1; cout m >> st; while (m--){ int v, w; cin >> v >> w; adj[v].push_back(w); adj[w].push_back(v); } for (int i = 1; i n >> m; for (int i = 1; i ch; mp[i..

1. [2748] 피보나치 수 2 (Bronze I) 더보기 4주차에서 이미 풀어본 문제이지만, 다시 풀어보면서 시간복잡도를 분석해봅시다. 피보나치 수는 \( F_{N} = \begin{cases} 0 & \text{if } N = 0 \\ 1 & \text{if } N = 1 \\ F_{N-1} + F_{N-2} & \text{otherwise} \end{cases} \)입니다. 위 방식을 나이브한 재귀로 구현할 때의 시간복잡도는 어떻게 될까요? 결론만 말하자면, 나이브한 재귀로는 \( O(F_{N}) \)의 시간이 걸립니다. \( F_{1} = 1 \)의 케이스까지 내려가야 답에 1이 더해지므로, 저 과정이 \( F_{N} \)번 반복되어야 우리가 원하는 답인 \( F_{N} \)이 나오겠죠. 그리고..

문제 정보 링크: https://www.acmicpc.net/problem/11813 난이도: Platinum I 분류: [자료구조 → 분리 집합 (DSU) → Small to Large] [오프라인 쿼리] 문제 요약 트리 \( T = (V, E) \)가 주어질 때, (초기 상태를 포함해) 간선을 하나씩 자를 때마다 아래 문제의 답을 출력하면 됩니다. 임의의 두 정점 \( v \neq w \)에 대해, \( v \)에서 \( w \)로 가는 경로에 속한 간선들의 가중치를 XOR한 값이 0인 정점쌍 \( (v, w) \)의 개수. (\( (v, w)\)와 \( (w, v) \)는 같은 것으로 취급한다.) 풀이 간선을 자르기만 합니다. 보통 이럴 때 하는 건 '쿼리를 역순으로 처리하면서 간선을 잇기'가 되죠..

문제 정보 링크: https://www.acmicpc.net/problem/16139 난이도: Silver I 분류: [누적합] 문제 요약 문자열 \( S \)에서 \( \alpha \)라는 알파벳이 \( [L, R] \) 구간 내에서 총 몇 번 등장하는지 묻는 문제입니다. + 쿼리 문제로, \( [L, R], \alpha \)가 바뀝니다. 서브태스크 1 (50점) 직접 \( [L, R] \) 구간을 돌리면서 \( \alpha \)의 등장 횟수를 세면 됩니다. 시간복잡도는 \( O(Q|S|) \)회입니다. void Main(){ string s; cin >> s; int q; cin >> q; while (q--){ char ch; int l, r; cin >> ch >> l >> r; int ans =..

문제 정보 링크: https://www.acmicpc.net/problem/15372 난이도: Bronze III 분류: [수학 → 사칙연산] 문제 요약 \( N \)이 주어졌을 때, \( N^2 \)의 배수인 가장 작은 \( K \)를 찾는 문제입니다. 풀이 \( N^2 \)의 배수 중 가장 작은 수는 당연히 \( N^2 \)입니다. 그러니 \( N^2 \)을 출력해주면 됩니다. 시간복잡도는 \( O(T \times 1) \)입니다. 코드 void Main(){ int t; cin >> t; while (t--){ ll n; cin >> n; cout