[Algorithm] 깊이 우선 탐색 목차 1. DFS란? 2. 그래프란? 그래프의 특징 그래프의 종류 그래프 용어 1. DFS란? 깊이 우선 탐색(Depth-First-search)은 그래프 완전 탐색 기법중 하나 그래프의 시작 노드에서 출발하여 탐색할 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 분기 쪽으로 이동하여 탐색을 수행하는 알고리즘 트리의 완전 탐색에 사용된다. 깊이 우선탐색 특징 기능 특징 시간 복잡도 (노드 -V, 엣지 - E) 그래프 완전 탐색 - 재귀 함수로 구현 - 스택 자료구조 이용 O(V+E) DFS는 사실상 재귀함수문제와 다름없다. 재귀 함수를 이용하므로 스택오버플로에 유의해야 한다. DFS를 이용하여 풀 수 있는 문제는 단절점 찾기, 단절선 찾기, 사이클 찾기, 위상..

위 문제는 DFS풀이의 가장 기본적인 문제이다. 문제를 풀기에 앞서 풀이 순서를 짚어보자. 1. 최대 정점의 개수와 문제풀이 시간을 대조해본다. - 문제 풀이 시간은 3초이다. 최대 노드의 개수는 1000개로 n^2의 복잡도로 문제를 풀어도 충분히 시간이 남는다. 2. 해당 그래프를 직접 그려본다. - 첫 예시의 그래프를 만들어보자면 다음과 같다. (혼을 담아 정성스럽게 그려보았다) 3. 이처럼 두개의 그래프가 그려지는것을 확인할 수 있다. 이를 코드로 작성하기 위한 슈도코드를 작성해본다. n(노드 개수) , m(엣지 개수) A(그래프 데이터 저장 인접 리스트) visited(방문 기록 저장 배열) for(n만큼 반복 {A 인접 리스트의 각 ArrayList초기화} for(m의 개수만큼 반복하기) { A..

package loop; import java.util.Random; public class Ex08 { public static void main(String[] args) { Random ran = new Random(); int begin = ran.nextInt(10)+1; int end = ran.nextInt(10)+100; System.out.println("begin : %d, end : %d\n, begin , end"); // 두 정수의 합계 구하기 int total = 0; int n1 = begin; while(n1

package loop; import java.util.Random; public class Ex07 { public static void main(String[] args) { // 탐색 //순차탐색(sequential search) : 처음부터 순서대로 하나씩 값을 비교해나가는 방식 //이진탐색(binary search) : 중간값을 찾아나가면서, 값의 범위를 좁혀나가는 방식 Random ran = new Random(); int cnt = 0; int min =1; int max = 10000; int answer = ran.nextInt(max) +1; int seq = min; while(true) { cnt++; if(seq == answer ) break; else {seq++;} } Sys..