본문 바로가기
반응형

PS/백준

 (329)
[BOJ] 백준 1260 DFS와 BFS (Swift) 문제 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를 사용하여 풀 수 있는 문제입니다. 주의할 점은 정점 번호가 작은 순으로 방문해야 하기 때문에, 인접 그래프를 정렬해주었습니다. DFS, BFS를 수행하면서 노드를 방문하게 될 떄, 해당 노드의 번호를 출력하도록 하였습니다. DFS를 먼저 수행하기 떄문에, DFS를 수행한 후, 방문 여부를 알 수있는 배열을 전부 fals..
[BOJ] 백준 2606 바이러스 (Swift) 문제 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 풀이 DFS/BFS를 사용해서 풀이할 수 있는 문제입니다. 둘 중 아무거나 사용해도 상관없어서 두 방법으로 모두 풀어보았습니다. 먼저 정점의 개수만큼 방문 여부를 알 수 있는 Bool 배열을 선언해주었습니다. 탐색을 마친 후, 방문 배열을 확인하여 방문횟수를 구한 후, 1번 컴퓨터는 제외해야 하므로 1을 빼고 출력해주었습니다. 소스코드 후기 DFS/BFS의 기초적인 문제였습니다.
[BOJ] 백준 24445 알고리즘 수업 - 너비 우선 탐색 2 (Swift) 문제 https://www.acmicpc.net/problem/24445 24445번: 알고리즘 수업 - 너비 우선 탐색 2 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net 풀이 https://dev-mandos.tistory.com/255 [BOJ] 백준 24444 알고리즘 수업 - 너비 우선 탐색 1 (Swift) 문제 https://www.acmicpc.net/problem/24444 24444번: 알고리즘 수업 - 너비 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,..
[BOJ] 백준 24444 알고리즘 수업 - 너비 우선 탐색 1 (Swift) 문제 https://www.acmicpc.net/problem/24444 24444번: 알고리즘 수업 - 너비 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양방 www.acmicpc.net 풀이 기본적인 BFS 알고리즘으로 풀이할 수 있는 문제입니다. BFS를 구현할 때, Queue 자료구조를 사용하는데, Swift에서는 지원하지 않기 때문에 직접 구현해주어야 합니다. Queue의 pop 연산을 index로 구현하여 풀이했습니다. https://dev-mandos.tistory.com/190 [자료구조]..
[BOJ] 백준 24480 알고리즘 수업 - 깊이 우선 탐색 2 (Swift) 문제 https://www.acmicpc.net/problem/24480 24480번: 알고리즘 수업 - 깊이 우선 탐색 2 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net 풀이 https://dev-mandos.tistory.com/253 [BOJ] 백준 24479 알고리즘 수업 - 깊이 우선 탐색 1 (Swift) 문제 https://www.acmicpc.net/problem/24479 24479번: 알고리즘 수업 - 깊이 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,..
[BOJ] 백준 24479 알고리즘 수업 - 깊이 우선 탐색 1 (Swift) 문제 https://www.acmicpc.net/problem/24479 24479번: 알고리즘 수업 - 깊이 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net 풀이 깊이 우선 탐색(DFS)에 대한 이해가 있다면 쉽게풀 수 있는 문제였습니다. 방문 여부를 알 수 있는 Int 배열을 생성하고 0으로 초기화 해주었습니다. dfs로 방문을 하면서 현재 노드를 방문하지 않았다면, 순서에 1을 더해주고 Int 배열의 값에 순서를 넣어주었습니다. 또한, 현재 노드에서 방문할 수 있는 노드..
[BOJ] 백준 17299 오등큰수 (Swift) 문제 https://www.acmicpc.net/problem/17299 17299번: 오등큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 풀이 오큰수 문제와 거의 동일한 문제이고, 스택 자료구조를 사용해서 풀이할 수 있습니다. 오큰수는 수의 크기를 갖고 비교했지만, 이 문제는 수가 나타난 횟수에 따라서 비교해주면 되는 문제입니다. 횟수를 구하기 위해 Dictionary를 사용하였습니다. 스택의 마지막 요소보다 현재 요소가 더 많이 나타났다면, Stack을 pop 해주고 해당 인덱스의 값을 현재 요소로 바꿔주었습니다. 소스코드 후기 이 문제..
[BOJ] 백준 17298 오큰수 (Swift) 문제 https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 풀이 스택 자료구조를 사용해서 풀이할 수 있는 문제입니다. 스택에 수를 하나씩 넣어주고, 스택의 Top이 현재 수보다 작다면 현재 수가 오큰수가 될 것입니다. 예를들어 5, 2, 7 이란 수가 있고, 현재 스택에 5, 2 까지 들어오고 7을 살펴보고 있다면 7이 현재 스택의 Top인 2보다 크기 때문에 2의 오큰수는 7이되고 2를 pop 해줍니다. 7이 현재 스택의 Top인 5보다 크기 때문에 5의 오..
반응형

티스토리툴바