ALOHA - 2022/ALOHA - 중급반 (2022 1학기)
-
중급반 8주차 풀이 - 세그먼트 트리ALOHA - 2022/ALOHA - 중급반 (2022 1학기) 2022. 5. 31. 13:05
1. [2042] 구간 합 구하기 (Gold I) 더보기 Segment Tree (Point Update & Range Sum Query) 연습 문제입니다. const int N = 1048576; ll seg[2097160]; void upd(int pos, ll val){ pos += N-1; seg[pos] = val; pos >>= 1; while (pos){ seg[pos] = seg[pos= 1; ed >>= 1; } return res; } void Main(){ int n, m, k; cin >> n >> m >> k; int q = m+k; for (int i = 1; i > seg[i+N-1]; } for (int i = N-1; i >= 1; i--){ seg[i] = seg[i po..
-
중급반 7주차 풀이 - DSU, MSTALOHA - 2022/ALOHA - 중급반 (2022 1학기) 2022. 5. 25. 15:34
1. [1717] 집합의 표현 (Gold IV) 더보기 Union-Find 구현 문제입니다. 특별한 것도 없습니다. int par[1000020]; int fnd(int a){ if (par[a] == a){ return a; } return par[a] = fnd(par[a]); } void uni(int a, int b){ par[fnd(a)] = fnd(b); } void Main(){ int n, q; cin >> n >> q; for (int i = 0; i > typ; if (typ == 0){ int a, b; cin >> a >> b; uni(a, b); } if (typ == 1){ int a, b; cin >> a >> b; cout n >> m; for (int i = 1; i arr..
-
중급반 6주차 풀이 - 최단경로 (BFS, 다익스트라)ALOHA - 2022/ALOHA - 중급반 (2022 1학기) 2022. 5. 18. 16:35
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..
-
중급반 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..
-
중급반 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..
-
중급반 3주차 풀이 - 이진 탐색, 파라메트릭 서치, 두 포인터ALOHA - 2022/ALOHA - 중급반 (2022 1학기) 2022. 5. 4. 00:21
A. [11053] 가장 긴 증가하는 부분 수열 (Silver II) 더보기 \( DP_{i} := \) \( i \)번째 원소로 끝나는 LIS 로 정의하면, \( DP_{i} = \max_{A_{j} \lt A_{i}} DP_{j} + 1 \)로 점화식을 세울 수 있습니다. 초기값은 \( DP_{i} = 1 \)이고, 문제의 답은 \( \max_{1 \le i \le N} DP_{i} \)입니다. int arr[1020], dp[1020]; void Main(){ int n; cin >> n; for (int i = 1; i > arr[i]; } for (int i = 1; i n; for (int i = 1; i > arr[i]; } sort(arr+1, arr+n+1); int q; cin >> q..
-
중급반 2주차 풀이 - 그리디, DP, 분할 정복ALOHA - 2022/ALOHA - 중급반 (2022 1학기) 2022. 5. 2. 19:56
A. [1931] 회의실 배정 (Silver II) 더보기 가장 빨리 끝나는 회의를 진행하면 됩니다. 이러면 선택의 폭이 더 넓기 때문에, 최적해가 잘 구해집니다. 주의할 점은, 가장 빨리 끝나는 회의가 여러개라면, '시작 시간이 가장 빠른 회의'를 선택해야 합니다. 이는 [12, 12], [10, 12] 같은 경우를 잘 처리하기 위한 추가 작업입니다. (만약 저 순서대로 저장되었다면 [12, 12]를 선택 → 12시 이후의 회의가 없음 → 종료 → 출력 = 1이 됩니다.) 시간복잡도는 \( O(N \log N) \)입니다. pl2 arr[100020]; void Main(){ int n; cin >> n; for (int i = 1; i > arr[i].fr >> arr[i].sc; } sort(arr..
-
중급반 1주차 풀이 - Brute ForceALOHA - 2022/ALOHA - 중급반 (2022 1학기) 2022. 4. 30. 01:18
1. [2309] 일곱 난쟁이 (Bronze I) 더보기 정답인 7명을 다 고르는 건 힘든 작업입니다. 그러니까 정답이 아닌 2명을 골라봅시다. 9명의 키의 합 - (빼는 2명의 키의 합) = 100인 2명을 고르면 되고, \( O(N^2) \)에 해결할 수 있습니다. int arr[10]; void Main(){ int n; cin >> n; int sum = 0; for (int i = 1; i > arr[i]; sum += arr[i]; } sort(arr+1, arr+10); for (int i = 1; i > k; for (int i = 1; i arr[i][j]; } } ll ans = 1e18, mxp = 0; for (int h = 0; h t; while (t--){ ll n; cin >..