코딩연습이 좋아서/이론이 좋아서

Recursive, Tree, Graph(DFS, BFS 기초) - Tree 말단노드까지의 가장 짧은 경로(BFS)

루트노드에서 말단노드까지 가는데 이동하는 횟수를 즉 간선(에지)의 개수를 길이로 한다.import java.util.LinkedList;import java.util.Queue;class Node { int data; Node lt, rt; public Node(int val) { this.data = val; this.lt = null; this.rt = null; }}public class Main { Node root; public static int BFS(Node root) { Queue queue = new LinkedList(); int L = 0; queue.add(root); ..

Recursive, Tree, Graph(DFS, BFS 기초) - Tree 말단노드까지의 가장 짧은 경로(DFS)

루트노드에서 말단노드까지 가는데 이동하는 횟수를 즉 간선(에지)의 개수를 길이로 한다.class Node { int data; Node lt, rt; public Node(int val) { this.data = val; this.lt = null; this.rt = null; }}public class Main { Node root; public static int DFS(int L, Node root) { if (root.lt == null && root.rt == null) return L; else return Math.min(DFS(L + 1, root.lt), DFS(L + 1, root.rt)); ..

Recursive, Tree, Graph(DFS, BFS 기초) - 송아지 찾기 1(BFS : 상태트리탐색)

설명현수는 송아지를 잃어버렸다. 다행히 송아지에는 위치추적기가 달려 있다.현수의 위치와 송아지의 위치가 수직선상의 좌표 점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 다음과 같은 방법으로 이동한다.송아지는 움직이지 않고 제자리에 있다.현수는 스카이 콩콩을 타고 가는데 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수 있다.최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 프로그램을 작성하세요.입력첫 번째 줄에 현수의 위치 S와 송아지의 위치 E가 주어진다. 직선의 좌표 점은 1부터 10,000까지이다.출력점프의 최소횟수를 구한다. 답은 1이상이며 반드시 존재합니다.예시 입력 1 5 14예시 출력 13 import java.util.LinkedList;import j..

Recursive, Tree, Graph(DFS, BFS 기초) - 이진트리 레벨탐색(BFS : Breadth-First Search)

import java.util.LinkedList;import java.util.Queue;class Node { int data; Node lt; Node rt; public Node(int data) { this.data = data; this.lt = null; this.rt = null; }}public class Main { private Node root; public static void BFS(Node root) { Queue queue = new LinkedList(); queue.offer(root); int L = 0; while (!queue.isEmpty()..

Recursive, Tree, Graph(DFS, BFS 기초) - 부분집합 구하기(DFS)

public class Main { static int n; static int[] ch; public static void DFS(int L) { if (L == n + 1) { String tmp = ""; for (int i = 1; i 0) System.out.println(tmp); } else { ch[L] = 1; DFS(L + 1); ch[L] = 0; DFS(L + 1); } } public static void main(String[] args) { n = 3; ch = new i..

Recursive, Tree, Graph(DFS, BFS 기초) - 이진트리순회(DFS : Depth-First Search)

class Node { int data; Node lt, rt; public Node(int val) { this.data = val; this.lt = null; this.rt = null; }}public class Main { Node root; public static void DFS(Node root) { if (root == null) return; else { System.out.print(root.data + " "); DFS(root.lt); DFS(root.rt); } } public static void mai..

Recursive, Tree, Graph(DFS, BFS 기초) - 피보나치 재귀(메모이제이션)

public class Main { static int[] fibo; public static int DFS(int n) { if (fibo[n] > 0) return fibo[n]; if (n == 1) return fibo[n] = 1; else if (n == 2) return fibo[n] = 1; else return fibo[n] = DFS(n - 2) + DFS(n - 1); } public static void main(String[] args) { int n = 45; fibo = new int[n + 1]; DFS(n); for (int i = 1; i - 더 빨리 ..

Recursive, Tree, Graph(DFS, BFS 기초) - 팩토리얼

public class Main { public static int DFS(int n) { if (n == 1) return 1; else return n * DFS(n - 1); } public static void main(String[] args) { System.out.println(DFS(5)); }}

Recursive, Tree, Graph(DFS, BFS 기초) - 이진수 출력(재귀)

public class Main { public static void DFS(int n) { if (n == 0) { return; } else { DFS(n / 2); System.out.print(n % 2 + " "); } } public static void main(String[] args) { DFS(11); }}

Recursive, Tree, Graph(DFS, BFS 기초) - 재귀함수(스택프레임)

public class Main { public static void DFS(int n) { if (n == 0) { return; } else { DFS(n - 1); System.out.print(n + " "); } } public static void main(String[] args) { DFS(3); }}- 스택 프레임이 쌓여 DFS 함수가 호출되어 쌓여있다가 나중에 출력이 된다. 그래서 결과가 1 2 3 으로 나온다