김진우 개발일지 블로그

#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 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

R은 배열의 뒤집기, D는 배열 맨 앞 요소의 삭제다. R와 D가 들어온 만큼 실제로 배열을 조작하는 작업은 O(N)의 시간이 걸려 시간 초과가 나온다. 실제로 뒤집는 것이 아닌 isReversed 변수를 만들고, 삭제도 실제로 삭제하는게 아니라 시작과 끝 인덱스를 저장해 맨 마지막에 한꺼번에 배열을 수정하는 것이 바람직하다. #include #include #include #include using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); int T; cin >> T; for (int t = 0; t > func; int N; cin >> N; ..

#include #include #include using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; for (int i = 0; i > M >> Q; queue> tasks; priority_queue maxHeap; for (int j = 0; j > num; tasks.emplace(num, j); maxHeap.push(num); } int answer = 0; while (true) { int val..

#include #include using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); int N, K; cin >> N >> K; vector p; for (int i = 1; i "; break; } int index = prevIndex + K - 1; if (size

문제를 해석하자면 다음과 같다.입력은 N와, N개의 수로 이루어진 1~N의 중복 없는 수열을 받는다.숫자 1부터 N까지 순서대로 스택에 push와 pop을 반복하는데, 이 때 입력받은 수열과 동일한 순서대로 숫자를 pop 하는 과정을 +와 -로 표시하면 된다.#include #include #include #include using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; vector nums(N); vector answer; for (int i = 0; i > nums[i]; } stack numStack; int lastNum = 0; for (int i = 0; i