Hello, There

https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 이진탐색은 배열이 정렬된 상태에서 원하는 값을 찾을 때 사용할 수 있는 알고리즘이다. 정렬된 배열의 중앙에 위치한 값을 선택하고, 찾고자 하는 수(target)과 그 크기를 비교한다. 배열 A의 길이가 N이라면 중앙값의 위치(mid)는 0(start) + N-1(end) 을 2로 나눈 수가 된다. 중앙값이 타겟보다 크다면, 찾고자 하는 수는 중앙값 ..

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의 경우, PriorityQueue를 원소로 갖는 배열을 인접리스트로 만들었다. 인접리스트 내의 PriorityQueue에서 연결된 노드를 작은..

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 깊이를 우선적으로 탐색하는 DFS와 달리 BFS는 넓이를 우선적으로 탐색한다. DFS가 어떤 노드에서 갈 수 있는 다음 노드, 그리고 다음 노드에서 갈 수 있는 다다음 노드를 찾아 깊숙하게 탐색을 이어간다면, BFS는 어떤 노드에서 갈 수 있는 여러 노드들을 모두 방문하고 나서야 다음 깊이의 노드들을 탐색한다. 이를 위해 BFS는 queue를 사용하여 구현하며 특정 목표 노드까지의 최단 거리를 구하기에 용이하다. 2178번 역시..

https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net https://seungboo.tistory.com/27 백준/2606번/Java - 바이러스 (DFS) https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트 seungboo.tistory.com 위의 260..

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net 11724번 문제처럼 DFS를 활용하면 간단하게 풀 수 있는 문제. https://seungboo.tistory.com/26 1번 컴퓨터에서 시작한다는 조건이 있으므로 1번 컴퓨터에서부터 탐색을 시작하여 탐색이 종료될 때까지 방문한 노드의 개수를 카운팅하면 된다. import java.io.*; import java.util.ArrayList; import java.util.StringTokenizer..

https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어 www.acmicpc.net 연결 요소 (Connected Component)의 개수를 구하는 문제. 문제에서는 정점의 개수 N과 정점을 잇는 간선의 개수 M, 각 간선의 양 끝점 u, v가 주어진다. 즉 각 노드와 노드의 위치, 이를 잇는 간선을 알려준 것이다. 예제를 따라서 그림을 그려보면 1-2-5가 연결되어있고, 3-4-6이 연결되어 있다는 것을 알 수 ..