푸으름

✏️ 문제 링크https://www.acmicpc.net/problem/24416  ✏️ 문제 설명  ✏️ 문제 풀이피보나치 함수를 재귀함수와 동적프로그래밍으로 계산했을 때 각 함수를 얼마나 호출하는지에 관한 문제입니다.전역변수로 cnt1을 선언하고 재귀함수 부분에서 return (fib(n - 1) + fib(n - 2));을 호출하기 직전에 cnt1에 1을 더해주시면 됩니다. 차피 n==1일때나 2일때까지 가고나면 알아서 계산을 다 해주기 때문에 이렇게 재귀 호출 횟수를 구할 수 있습니다 동적 프로그래밍으로 하는 계산횟수는 for문을 돌리기보다 쉽게 생각해보면 n-2번 호출하게 됩니다.fib(n)값을 구하기 전에 미리 fib(1)과 fib(2)값을 지정해놓기 때문에 위의 사진처럼 for문을 돌린다면 ..

✏️ 문제 링크https://www.acmicpc.net/problem/24444  ✏️ 문제 설명  ✏️ 문제 풀이bfs를 구현하는 문제입니다. visited배열을 만들어서 각 정점의 방문 여부를 체크해주고, order배열을 만들어서정점들의 방문 순서들을 저장해 주면 됩니다. 오름차순으로 인접 정점을 방문해줘야 하므로 sort 정렬을 해줍니다.  ✏️ 문제 코드#include#include#include#includeusing namespace std;int N, M, R;vector>mlist;bool visit[100001];int order[100001];int cnt = 1;int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NU..

✏️ 문제 링크https://www.acmicpc.net/problem/24479 ✏️ 문제 설명  ✏️ 문제 풀이단순 dfs를 구현하는 문제입니다. 다만 dfs를 탐색하면서 order[next] = order[node]+1로 하면 틀릴 수 있기 때문에방문 순서를 체크해주는 count변수를 전역 변수로 설정하고 코드를 구현했습니다.그리고 오름차순으로 방문을 해야하기 때문에 list를 각 노드마다 오름차순 정렬을 하였습니다.이차원배열로 돌릴까 고민을 해봤는데 너무 메모리를 많이 잡아먹을 것 같아서 사용하지 않았습니다.  ✏️ 문제 코드#include#include#includeusing namespace std;bool visit[100001];int order[100001];vector>list;void..