코딩 테스트39 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. cpp) 백준 1931: 회의실 배정 Problem https://www.acmicpc.net/problem/1931 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. Solution #include #include #include using namespace std; /* 빨리 시작한다고 해서 회의를 많이 할 수 있는 것이 아니다. 회의가 빨리 끝나고, 끝나자마자 다른 회의를 시작할 수 있다면.. 2023. 6. 8. cpp) 백준 11866: 요세푸스 문제 0 Problem https://www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net 1번부터 N번까지 N명의 사람들이 원을 이루며 앉아있다. 양의 정수 K가 주어질 때, 순서대로 K번째 사람을 제거한다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 나타낸 (N,K) 요세푸스 순열을 구하시오. Solution #include #include using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, k; ci.. 2023. 6. 8. cpp) 백준 11650: 좌표 정렬하기 Problem https://www.acmicpc.net/problem/11650 11650번: 좌표 정렬하기 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 2차원 평면에 점 N개가 주어졌다고 하자. 좌표를 x좌표가 증가하는 순으로, x좌표가 같다면 y좌표가 증가하는 순서로 정렬하시오. Solution #include #include using namespace std; struct info{ int x; int y; }; // 앞에 오는 a보다 뒤에오는 b가 더 크도록, 오름차순 정.. 2023. 6. 8. cpp) 백준 11050: 이항 계수 1 Problem https://www.acmicpc.net/problem/11050 11050번: 이항 계수 1 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 0 ≤ K ≤ N) www.acmicpc.net 자연수 N과 정수 K가 주어졌을 때 이항계수를 구하시오. Solution #include #include #include using namespace std; int cache[11][11]; int bino2(int n, int k){ // 기저 사례 if (k==0 || n==k) return 1; // cache[n][k] 값이 존재할 경우 if (cache[n][k]!=-1){ return cache[n][k]; } return cache[n][k] .. 2023. 6. 8. cpp) 백준 1929: 소수 구하기 Problem https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net M이상 N이하의 소수를 모두 출력하시오. Solution #include using namespace std; int arr[1000001]; void Primesieve(int m, int n){ // 배열 초기화 for(int i=2;i 2023. 6. 8. 이전 1 ··· 3 4 5 6 7 다음
