정화 코딩

https://www.acmicpc.net/problem/11054 #include #include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; vector a(n); for (int i = 0; i > a[i]; vector dp1(n); vector dp2(n); for (int i = 0; i a[j]) maxt = max(maxt, dp1[j]); } dp1[i] = maxt + 1; } for (int i = n - 1; i >= 0; i--) { in..

https://www.acmicpc.net/problem/32649 #include #include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int a, b, k; cin >> a >> b >> k; vector ans; ans.push_back(a); ans.push_back(b); for (int i = a + 1; i = k) { for (int i = 0; i 캐어려운 정수론 문제인줄 알았는데 그냥 브루트포스 문제였다 ㅎㅎ;;핵심 포인트는 d는 A의 배수이면서 B의 약수여야 한다는 것이다. 그런데 A와 B의 범위가 그렇게 ..

https://www.acmicpc.net/problem/1359 #include #include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); long long f[11]; f[0] = 1; for (int i = 1; i > n >> m >> k; cout.precision(10); int ans = 0; for (int i = k; i 수식은 아래와 같다.시그마 안에 있는 식을 정리하면 아래와 같다.그런데 아래와 같이 구현하면 WA를 받게 된다.for (int i = k; i 답을 이렇게 계산하면 8 7 1 를 입력했을 때 1.02290799..

9회차 - dp 피보나치 수 2https://www.acmicpc.net/problem/2748피보나치 수를 구하는 걸 재귀로 구현하게 되면 시간 복잡도가 O(2^n)이므로 n이 조금만 커져도 실행 시간이 기하급수적으로 늘어나게 됩니다. 이는 같은 피보나치 값을 여러 번 중복 계산하기 때문입니다. 예를 들어, fib(5)를 계산할 때 fib(3)이 두 번, fib(2)가 세 번 호출되는 식으로 불필요한 연산이 계속 발생합니다.따라서 중복 계산을 막기 위해 이전에 계산한 값들을 저장하고 활용해야 합니다. 이럴 때 사용하는 대표적인 방법이 동적 계획법(DP)를 사용하게 되는 것입니다.#include #include using namespace std;int main() { ios_base::sync_..

8회차 - BFS, DFS DFS와 BFShttps://www.acmicpc.net/problem/1260DFS, BFS 기본 문제입니다. 각 방식을 구현하고 방문하는 노드를 출력하면 됩니다.주의할 점 1. 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 택해야 한다는 것입니다. 따라서 저는 입력을 받은 후 각 정점에 연결된 정점들에 대해 정렬을 한 번씩 진행해주었습니다.주의할 점 2. 탐색 여부 배열을 공유한다면 초기화가 필요합니다.#include #include #include #include using namespace std;vector vst;vector> g;void dfs(int cur) { vst[cur] = true; cout q; q.push(..

7회차 - graph, tree, map and set  집합https://www.acmicpc.net/problem/11723다양한 방법으로 풀 수 있는 문제입니다.  1. set을 사용한 풀이단순히 문제에서 설명하는 대로 코드를 작성하면 됩니다.#include #include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int m, n; string op; cin >> m; set s; for (int i = 0; i > op; if (op == "add") { cin >> n; s.insert(..

6회차 - 재귀, 분할정복  재귀함수가 뭔가요?https://www.acmicpc.net/problem/17478글이 많아 약간 귀찮을 수 있지만 재귀의 개념을 익히기 좋은 문제입니다.#include using namespace std;int n;void f(int x) { if (x > n) { return; } else if (x == n) { for (int i = 0; i > n; cout   N과 M (1)https://www.acmicpc.net/problem/15649저는 백트래킹을 이용한 dfs 함수를 만들고 dfs 함수를 재귀적으로 호출하는 방식으로 구현했습니다.#include #include using namespace std;int n, m;v..

5회차 - 브루트포스, 이분탐색 수학은 비대면강의입니다https://www.acmicpc.net/problem/19532모든 x와 y에 대해서 조건을 체크해주면 됩니다.#include using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int a, b, c, d, e, f; cin >> a >> b >> c >> d >> e >> f; // -999부터 999까지 가능한 x, y 값을 전부 탐색 for (int x = -999; x 마인크래프트https://www.acmicpc.net/problem/18111높이를 계속 바꿔서 고정해놓고 계산하는 방식으로 구..