코딩 테스트39 [그래프] 너비 우선 탐색 (BFS) BFS 소개그래프는 노드와 간선을 이용한 비선형 데이터 구조입니다. 너비 우선 탐색(Breadth First Search)은 시작 노드와 거리가 가장 가까운 노드를 우선하여 방문하는 방식의 알고리즘 입니다. 여기서 거리는 시작 노드와 목표 노드까지의 차수를 말합니다. BFS 알고리즘은 루트 노드에서 가까운 노드부터 탐색하므로, 가중치가 없는 그래프에서 최단 경로를 보장합니다. 알고리즘 동작 방식BFS는 주로 큐를 이용해 구현합니다. 일단 시작 노드를 정하고, 큐에 시작 노드를 푸시합니다.시작 노드를 큐에 푸시하면서, 방문 처리를 합니다.큐에 있는 노드는 이미 방문 처리했고, 그 노드와 인접한 노드는 아직 탐색하지 않은 상태입니다.이후, 큐가 비어있는지 확인합니다.큐가 비었다면, 방문할 수 있는 모든 노드.. 2025. 4. 7. cpp) 백준 9095: 1, 2, 3 더하기 Problem https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net Solution #include #include using namespace std; int t; // 테스트케이스 수 int n; // 정수 n int cache[12]; // 방법의 수 저장 int main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); memset(cache,0,sizeof(int)); // 메모리 초기화 cache[1]=1; cache[2]=2; cache[3]=4; cin >> t; for(int i=0.. 2023. 7. 21. cpp) 백준 1966: 프린터 큐 Problemhttps://www.acmicpc.net/problem/1966 1966번: 프린터 큐여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에www.acmicpc.net Solution#include#includeusing namespace std;int main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); int t; // 테스트케이스 수 int n, m, rank; // 문서의 개수, 궁금한 문서가 몇 번째 놓여있는가, 중요도 int cnt; .. 2023. 7. 17. cpp) 백준 1463: 1로 만들기 Problem https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net Solution #include #include using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(0);cout.tie(0); int n; cin >> n; int dp[10000001]; dp[0]=0; dp[1]=0; dp[2]=1; dp[3]=1; for(int i=4;i 2023. 7. 15. cpp) 백준 11399: ATM Problem https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net Solution #include #include using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; int people[n]; // 각 사람별 인출하는데 걸리는 시간 int time = 0; // 각 사람별 대기하는 시간 int waitingTime[n]; // 대기 합산 시간 int a.. 2023. 7. 12. cpp) 백준 18258: 큐 2 Problem https://www.acmicpc.net/problem/18258 18258번: 큐 2 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net Solution #include #include #include using namespace std; int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; queue q; while(n--){ string s; cin >> s; if(s=="push"){ int k; ci.. 2023. 7. 12. 이전 1 2 3 4 5 ··· 7 다음
