김진우 개발일지 블로그

#include using namespace std;int gcd(int a, int b) { while (b != 0) { int temp = a % b; a = b; b = temp; } return a;}int lcm(int a, int b, int gcd_value) { return a * b / gcd_value;}int main() { int a, b; cin >> a >> b; int gcd_value = gcd(a, b); int lcm_value = lcm(a, b, gcd_value); cout

#include #include #include using namespace std;void sieveOfEratosthenes(int N, vector& isPrime) { isPrime[0] = isPrime[1] = false; for (int i = 2; i > M >> N; vector isPrime(N + 1, true); sieveOfEratosthenes(N, isPrime); for (int i = M; i

#include #include #include using namespace std;bool isPrime(int num) { if (num > N; vector numbers(N); for (int i = 0; i > numbers[i]; } for (int i = 0; i

#include #include #include using namespace std;int main() { int cnt; cin >> cnt; vector divisors(cnt); for (int i = 0; i > divisors[i]; } sort(divisors.begin(), divisors.end()); int minDivisor = divisors[0]; int maxDivisor = divisors[cnt - 1]; cout

#include #include #include using namespace std;bool isValid(int row, int col, const vector& queen) { for (int i = 0; i & queen, int& count) { if (row == n) { count++; return; } for (int col = 0; col > n; vector queen(n, -1); solve(0, n, queen, count); cout

#include #include using namespace std;int main() { int T, n; cin >> T; while (T--) { cin >> n; vector dp(n + 1, 0); dp[0] = 1; for (int i = 1; i = 1) dp[i] += dp[i - 1]; if (i >= 2) dp[i] += dp[i - 2]; if (i >= 3) dp[i] += dp[i - 3]; } cout

Meet in the Middle 개념Meet in the Middle은 주어진 문제를 두 개의 부분 문제로 나누어 해결하는 방식입니다.완전 탐색을 할 경우, 모든 부분수열을 탐색하면 시간 복잡도가 O(2^N)이지만, Meet in the Middle을 사용하면 두 부분으로 나누어 O(2^(N/2))로 줄일 수 있습니다.이 방법을 이용하면 시간 복잡도를 획기적으로 줄일 수 있어 N=40 정도까지도 충분히 해결할 수 있습니다. Meet in the Middle을 3개 그룹으로 나누는 경우보통 2개 그룹으로 나누는 이유는:모든 부분집합을 구하는 데 O(2^N/2) 로 줄일 수 있기 때문입니다.그 후, unordered_map을 이용해 빠르게 대응되는 합을 찾을 수 있기 때문입니다.하지만,✅ 3개 그룹으로 나..

깊이 우선 탐색으로 경우의 수를 모두 구할 수 있다.#include #include using namespace std;void dfs(vector& s, vector& path, int idx) { if (path.size() == 6) { for (int x : path) cout > k; if (k == 0) break; vector s(k), path; for (int i = 0; i > s[i]; dfs(s, path, 0); cout