정화 코딩

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