계란 블로그

Ex) 1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다. - 신종 바이러스가 네트워크를 통해 전파된다. 한 컴퓨터가 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결된 모든 컴퓨터는 바이러스에 걸리게 된다. - 첫째 줄에는 컴퓨터의 수가 주어진다. - 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 순서쌍의 수, 셋째 줄에는 순서쌍이 나열되어있다. import java.util.*; public class Virus { static int MAX_COUNT = 101; static int[][] AdjMat = new int[MAX_COUNT][MAX_COUNT]; static int[] Visited = new int[M..

1. 합이 같은 부분집합 import java.util.*; public class Main { static String answer = "NO"; static int n, total = 0; boolean flag = false; public void DFS(int L, int sum, int [] arr){ if(flag == true) return;//재귀가 바로 끝나도록한다. if(sum > total / 2) return;// 확인할 필요가 없다. if(L == n){ if((total - sum) == sum){ answer = "YES"; flag = true; } } else{ DFS(L + 1, sum + arr[L], arr); // 무조건 + 1, arr[L]을 sum에 누적 DFS(..

1. 재귀함수 (스택 프레임) public class Main { public void DFS(int n){ if(n == 0) return; else{ System.out.println(n); DFS(n-1); } } public static void main(String[] args){ Main T = new Main(); T.DFS(5); return ; } } Note) - 실행 결과: 5 4 3 2 1 츨력 2. 이진수 출력 (재귀) import java.util.Scanner; public class Main { public void DFS(int n){ if(n == 0) return; else{ System.out.print(n + " "); DFS(n / 2); } } public sta..

Note) 그래프 - 그래프는 비선형 자료구조이다. -> 노드와 엣지로 구성된다. -> 방향성과 가중치(weight)를 줄 수 있다. -> 자바에서는 그래프를 구성하는 노드와 엣지가 제공되지 않는다. -> 직접 노드와 엣지를 구성해서 그래프를 만든다. - 비선형 자료구조에서 원하는 데이터 찾기 1) 데이터 하나 읽기 2) 다음 번에 읽을 것을 예약 (연결된 데이터를 찾기) 3) 예약된 것을 하나 꺼내기 4) 2,3 반복 - 예약 목록을 스택, 큐에 따라 다르게 탐색할 수 있다. -> 큐 이용: 너비우선탐색 (BFS) -> 스택 이용: 깊이 이용 탐색 (DFS) -> 두 가지는 탐색 순서만 다르다. Ex) BFS - Queue를 이용해서 만든다. import java.util.*; // 방향성과 가중치가 ..

1. 깊이 우선 탐색 (DFS, Depth-First Search) - 한 우물부터 깊이 판다. - 스택 이용 Ex) //깊이 우선 탐색 코드 public static void SearchDepthFirst(Node node) { Stack stack = new Stack(); stack.push(node); while(!stack.empty()) {// 스택이 비는 순간 끝 Node next = stack.pop(); System.out.println(next.data);// 방문해서 출력 for(Node child : next.children ) { stack.push(child); } } } 2. 너비 우선 탐색 (BFS, Breadth-First Search) - 여러 우물을 동시에 같은 깊이로 ..