DFS5 DFS (Discrete Fourier Series) 바로 알기 이산 푸리에 급수 (DFS)의 정의와 특성을 알아보고 예시를 통해 개념을 정리해봅시다. DFS (Discrete Fourier Series) DFS는 주기성을 갖는 discrete signal을 주파수 성분들의 합으로 표현하는 방법입니다. 이때, 각각의 주파수 성분은 특정 주파수에 해당하는 기저 함수 (basis function)로 표현할 수 있습니다. 위 신호에서 fundamental period는 $N$이고 fundamental frequency는 $\omega_0=2\pi / N$으로 표기합니다. 주파수 성분들은 fundamental frequency $\frac{2\pi}{N}$의 정수 배로 주어지기 때문에, DFS는 periodic signal을 조화적 관계를 갖는 (harmonically.. 2024. 6. 1. cpp) 백준 2606: 바이러스 Problem https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net Solution #include #include #include using namespace std; #define MAX 101 int n; // 정점의 수 int m; // 간선의 수 bool map[MAX][MAX]; // 네트워크 연결 bool visited[MAX]={0,}; // 정점 방문 여부 int cnt = 0; // 웜 바이러스에 걸린 컴퓨터 수 = 정답값 void df.. 2023. 7. 5. cpp) 백준 1012: 유기농 배추 Problem https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net Solution #include #include #include using namespace std; int t; // 테스트케이스 개수 int m, n; // 배추밭 가로, 세로 길이 int k; // 배추가 심어진 위치의 개수 bool map[50][50]; // 배추밭 void dfs(int row, int col){ // 인덱스 범위 초과 예방 if(row=50) return; if(co.. 2023. 7. 4. cpp) 백준 1260: DFS와 BFS Problem https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하시오. 방문할 수 있는 정점이 여러 개인 경우 정점 번호가 작은 것을 먼저 방문하고 더 이상 방문할 수 없는 경우 종료한다. 정점 번호는 1번부터 N번까지! Solution #include #include using namespace std; #define MAX 1001 int n, .. 2023. 6. 9. BFS, DFS 이해하기 Summary 대표 유형 : 경로탐색, 네트워크, 조합 만들기 BFS는 Queue 또는 LinkedList로 구현하고 DFS는 재귀함수로 구현한다. BFS는 모든 경우의 수를 한 걸음씩 수행하기 때문에 최악의 경우 시간 복잡도가 DFS에 비해 낮다. 이에 반해, DFS는 한 가지 경우의 수를 깊이 파기 때문에 최악의 경우에 시간 초과가 날 위험이 있다. Reference https://www.youtube.com/watch?v=BsYbdUnKZ-Y https://velog.io/@vagabondms/DFS-vs-BFS DFS vs BFS 넓고 깊은 알고리즘 세계는 DFS로? BFS로? velog.io 2023. 6. 8. 이전 1 다음
