th42500의 TIL

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 코드 효율 👉 메모리 : 15760 KB 👉 시간 : 164 ms 👉 코드 길이 (주석 및 print()함수 제외) : 1430 B ✔ 소스코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { //..

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 코드 효율 👉 메모리 : 14124 KB 👉 시간 : 124 ms 👉 코드 길이 (주석 및 print()함수 제외) : 1029 B ✔ 소스코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main ..

DFS (Depth-First Search) ✔ 그래프 탐색 알고리즘 탐색(Search)이란 많은 양의 데이터 내에서 원하는 데이터를 찾는 과정을 의미 ✔ DFS 특징 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘으로, 깊이 우선 탐색이라고도 불림 재귀적으로 구현 또는 후입선출 구조의 스택을 적용 트리일 경우 순회 방향 (번호 순서대로 진행) 시간복잡도는 O(V+E) 👉 V : 노드 수, E : 에지 수 ✔ 동작 과정 1️⃣ 탐색 시작 노드를 스택에 삽입하고 방문 처리 2️⃣ 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리, 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드 꺼내기 3️⃣ 더 이상 2️⃣번의 과정을 수행할 수 없을 때까지 반복 ..