ALOHA - 2022
-
고급반 5주차 풀이 - 아자아자 (10 / 15)ALOHA - 2022/ALOHA - 고급반 (2022 1학기) 2022. 5. 16. 10:29
+ 일부 문제에 대해 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
-
중급반 5주차 풀이 - DFS, BFS, 백트래킹ALOHA - 2022/ALOHA - 중급반 (2022 1학기) 2022. 5. 12. 13:24
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..
-
초급반 5주차 풀이 - DP, 시간복잡도ALOHA - 2022/ALOHA - 초급반 (2022 1학기) 2022. 5. 10. 08:30
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} \)이 나오겠죠. 그리고..
-
[2022.04.20.] GALAKSIJAALOHA - 2022/ALOHA - 오늘의 문제 (2022 1학기) 2022. 5. 9. 14:25
문제 정보 링크: 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) \)는 같은 것으로 취급한다.) 풀이 간선을 자르기만 합니다. 보통 이럴 때 하는 건 '쿼리를 역순으로 처리하면서 간선을 잇기'가 되죠..
-
[2022.04.17.] 인간-컴퓨터 상호작용ALOHA - 2022/ALOHA - 오늘의 문제 (2022 1학기) 2022. 5. 6. 16:05
문제 정보 링크: 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 =..
-
[2022.04.11.] A Simple Problem.ALOHA - 2022/ALOHA - 오늘의 문제 (2022 1학기) 2022. 5. 5. 12:46
문제 정보 링크: 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
-
고급반 4주차 풀이 - 파이팅ALOHA - 2022/ALOHA - 고급반 (2022 1학기) 2022. 5. 5. 01:27
1. [18857] 집 떠나와 열차 타고 (Diamond V) 더보기 BCC를 기준으로 생각해봅시다. 그래프가 선인장이기 때문에, BCC는 '간선 1개'이거나 '사이클 1바퀴'밖에 없습니다. 그러므로, \( 1 \Rightarrow N \)의 경로와 닿는 모든 BCC를 들고 온 뒤, 두 경우에 맞게 처리해주면 됩니다. 간선 1개: 그 간선을 자르면 됩니다. 사이클 1바퀴: 경로에 속한 가장 짧은 간선과 경로에 속하지 않은 가장 짧은 간선을 자르면 됩니다. 각 BCC별로 저 값을 구해둔 뒤, 최솟값을 찾아주면 됩니다. int n, m; vector adj[402020]; int ord=0, ind[402020]; stack stk; int cnt = 0, num[429020]; int dfs(int now..
-
중급반 4주차 풀이 - 냅색, 구간 DPALOHA - 2022/ALOHA - 중급반 (2022 1학기) 2022. 5. 4. 22:49
1. [1535] 안녕 (Silver II) 더보기 \( DP_{i, j} := \) \( i \)번째 사람까지 인사 여부를 결정했을 때, 체력을 최대 \( j \)만큼 써서 얻을 수 있는 최대 행복 이라고 정의합시다. 그럼 \( DP_{i, j} \)는 2가지 경우에 의해 결정됩니다. \( i \)번 사람에게 인사를 한다: \( DP_{i-1, j-L_{i}} + J__{i} \)만큼의 기쁨을 느낍니다. \( i \)번 사람에게 인사를 하지 않는다: \( DP_{i-1, j} \)만큼의 기쁨을 느낍니다. 문제의 답은 \( DP_{N, 99} \)가 됩니다. * 100의 체력을 쓰면 죽기 때문에 최대 체력은 99여야 합니다. 시간복잡도는 \( O(100N) \)입니다. pi2 arr[22]; int dp..