알고리즘(Java)/Recursive & Tree & Graph13 [알고리즘]BFS - 이진트리 순회 * BFS(Breadth-First Search) - 넓이(너비)우선 탐색: 레벨 탐색 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용한다. Queue를 사용해 레벨 순서대로 접근 가능하다. * BFS VS DFS 이진트리 레벨탐색 import java.util.LinkedList; import java.util.Queue; class Node { int data; Node lt, rt; public Node(int val) { data = val; lt = rt = null; } } public class Main { // BFS - 넓이 우선 탐색 Node root.. 2021. 8. 26. [알고리즘]DFS - 부분집합 구하기 자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램(공집합은 출력X) import java.util.Scanner; public class Subset { static int n; static int[] ch; public static void DFS(int k) { if (k==n+1) { String temp = ""; for (int i=1; i0) System.out.println(temp); // 공집합 출력 X } else { ch[k] = 1; // 왼쪽 방향 // 부분집합에 포함 DFS(k+1); ch[k] = 0; // 오른쪽 방향 // 부분집합에 포함X DFS(k+1); } } public static void main(String[] args) .. 2021. 8. 26. [알고리즘]DFS - Binary Tree(이진트리 순회) * DFS(Depth-First Search) - 깊이우선 탐색 이진트리 전위순회/중위순회/후위순회 출력 전위순회 출력 : 1 2 4 5 3 6 7 (부모 - 왼쪽자식 - 오른쪽자식) 중위순회 출력 : 4 2 5 1 6 3 7 (왼쪽자식 - 부모 - 오른쪽자식) 후위순회 출력 : 4 5 2 6 7 3 1 (왼쪽자식 - 오른쪽자식 - 부모) class Node { int data; // 노드 data 값 Node lt, rt; // 왼쪽자식의 주소, 오른쪽자식의 주소 public Node(int val) { this.data = val; this.lt = this.rt = null; } } public class Main { Node root; public void DFS(Node root) { if (r.. 2021. 8. 26. [알고리즘]Recursive - Fibonacci(피보나치) 피보나치 수열을 출력하는 프로그램 *피보나치 수열 : 앞의 2개의 수를 합하여 다음 숫자가 되는 수열 예) 7이 입력되면 1 1 2 3 5 8 13을 출력 1) 항목 전체 출력 - 메모이제이션 import java.util.Scanner; public class Main { // 메모이제이션 static int[] fibo; public static int fibonacci(int n) { if (fibo[n]>0) return fibo[n]; // 배열에 값이 이미 있다면 그 값 return if (n==1) return fibo[n] = 1; // 첫 번째 항 else if (n==2) return fibo[n] = 1; // 두 번째 항 else return fibo[n] = fibonacci(n-.. 2021. 8. 25. [알고리즘]Recursive - Factorial(팩토리얼) 자연수 N이 입력되면 N!를 구하는 프로그램 예) 5! = 5*4*3*2*1=120 import java.util.Scanner; public class Main { public static int factorial(int n) { if (n==1) return 1; else return n * factorial(n-1); } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); System.out.println(factorial(n)); } } 결과 5 120 2021. 8. 25. [알고리즘]Recursive - 이진수 출력 10진수 N이 입력되면 2진수로 변환하여 출력하는 프로그램 import java.util.Scanner; public class Main { public static void recursive(int n) { if (n==0) return; else { recursive(n/2); System.out.print(n%2); } } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); recursive(n); } } 결과 11 1011 2021. 8. 25. 이전 1 2 3 다음
