Categories(74)
-
백준 14621번, 나만 안되는 연애 풀이
문제 백준 14621번 풀이 빨간색 파란색을 잇는 간선을 제외하고 모두 제거합니다. 남은 간선을 가지고 정점을 모두 연결시킬 수 있는 MST (최소 스패닝 트리)를 만들면 됩니다. 정렬하는데 $ O(MlogM) $, 연결하는데도 $ O(MlogM) $이 걸리니 시간 복잡도 $O(MlogM)$에 해결할 수 있습니다. MST를 구하는 방법 (백준 1197번, 최소 스패닝 트리(MST)를 구하는 크루스칼 알고리즘) 소스코드 #include #define all(v) v.begin(), v.end() using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair pii; typedef pair pll; typedef ..
2020.12.25 -
백준 15918번, 랭퍼든 수열쟁이야!! 풀이
문제 백준 15918번 풀이 $ x $와 $ y $ 자리가 주어집니다. 문제에서 같은 수는 수열에서 "2번" 나오고, 같은 수 ($ k $) 사이의 원소 개수가 $ k $가 된다고 하였으니, $ x $와 $ y $ 자리에 넣을 수는 $ y - x + 1 $로 정해집니다. 나머지 수를 채우는 방법은 dfs를 사용하여 $ 2^(12) $만큼 돌면서 조건에 맞게 수열을 채워주면 됩니다. 시간 복잡도는 $ O(2^N) $이 됩니다. 소스코드 #include #define all(v) v.begin(), v.end() using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair pii; typedef pair pll;..
2020.12.22 -
백준 1644번, 소수의 연속합 풀이
문제 백준 1644번 풀이 에라토스테네스 체를 사용하여 구간 $[2, N]$ 사이의 모든 소수를 구해줍니다. 구한 소수를 배열에 오름차순으로 두고, 그 배열의 길이를 $ K $로 둡니다. 어떤 구간이 $ N $이 되는지 찾아봅시다. 첫번째로는 누적합을 사용하여 모든 $ i, j (1 \leq i \leq j \leq N) $에 방문하여 $ psum[j] - psum[i] = N$인지 확인해주면 $ O(K^2) $에 가능합니다. 하지만, $ N $의 범위가 $ 4,000,000 $이므로 $ K $가 $ 10,000 $을 넘어가서 제곱 풀이는 사용할 수 없습니다. 누적합에서는 모든 $i, j$를 방문하지만, 투포인터로 가능한 $i, j$만 빠르게 탐색할 수 있습니다. 투포인터의 왼쪽 포인터를 $ L $, 오..
2020.12.21 -
자동 자가진단 v0.2.10 출시 (2020.12.15 작동)
https://github.com/eduro-hcs/jaga_jindan/releases/tag/v0.2.10Release Release v0.2.10 · eduro-hcs/jaga_jindan자가진단 웹 구조 변경에 따른 업데이트github.com
2020.12.15 -
CLion 설치와 WSL 설정하기
CLion에는 컴파일러가 내장되어 있지 않으므로, Visual Studio의 MSVC, MinGW에서 gcc(g++)을 잡아 사용합니다. 하지만 MSVC의 경우 한글 폴더가 있으면 깨질뿐더러 온라인 저지 사이트에서는 대부분 gcc를 사용하니 동일한 답을 보장하지 않는 경우도 생깁니다. 일부 분들은 MinGW에서 C++17, 20에서 일부 비표준 헤더(bits/stdc++.h)들을 불러오지 못하는 오류를 겪는 것을 보았습니다. 그래서 오늘은 윈도우에서 제공하는 WSL(Windows Subsystems for Linux)로 Linux 환경의 gcc를 사용해 C(C++)를 컴파일하는 방법에 대해 다뤄보겠습니다. 우선 CLion은 JetBrains에서 제공하는 IDE입니다. 유료이기 때문에 30일 체험판을 받아..
2020.12.12 -
백준 20312번, CPU 벤치마킹 풀이
문제 백준 20312번 풀이 CPU $ i + 1$번째의 $ j $행은 CPU $ i $번째 $ j $행의 $ m_{i} $배 입니다. 따라서, $ i + 1 $번째 CPU 행의 합 = ($ i $번째 CPU 행의 합 + 1) * $ m_{i} $이 됩니다. 이전 행의 값을 계산해두면, 하나를 구할 때 $ O(1) $이므로, 모두 다 구해주는데 $ O(N) $이 걸리겠네요. 소스코드 #include #define all(v) v.begin(), v.end() using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair pii; typedef pair pll; typedef vector vi; typedef v..
2020.12.11