하다보면 늘겠지

루트 노드 1에서 말단 노드까지의 길이 중 가장 짧은 길이를 구하시오.(최단 거리는 BFS) import java.util.*; class Node { int data; Node lt, rt; //자식 노드들의 주솟값 public Node(int val) { data=val; lt=rt=null; } } public class Main { Node root; public int BFS(Node root) { Queue Q = new LinkedList(); Q.offer(root); int L = 0; while(!Q.isEmpty()) { //레벨의 길이를 구하자! int len = Q.size(); //1 2 4 8 .... for(int i = 0; i < len; i++) { Node cur = ..

루트 노드 1에서 말단 노드까지의 길이 중 가장 짧은 길이를 구하시오. 가장 짧은 경로를 DFS로 푸는건 매우 비효율적이나 학습을 위한 문제풀이임. import java.util.*; class Node { int data; Node lt, rt; public Node(int val) { data=val; lt=rt=null; } } public class Main { Node root; public 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)); } public static void main(String[] ..

현수의 위치에서 3갈래로 (앞으로 1,뒤로 1, 앞으로 5) 레벨 탐색하면된다. 이동한 위치에 대해서 방문처리 해주는 배열이 필요하다. - 길이는 10001 여기서 방문처리의 이유는 효율성 때문이다. 5번 위치에서 뻗어나가다가 5번 위치가 되었을 때 그 5번 위치에 또 탐색하는 것은 비효율적이다. import java.util.*; public class Main { int answer = 0; //3가지 점프 종류 int[] dis = {1, -1, 5}; //방문했던 위치인지 확인하는 배열 int[] ch; Queue Q = new LinkedList(); public int BFS(int s, int e) { //좌표는 1~10000 사이임 ch = new int[10001]; //처음 현수의 위치..

아래 그림과 같은 이진트리를 레벨탐색으로 출력하세요. 뺀 다음 데이터 찍고 자식들을 넣은 다음 레벨업 시켜 -> 계속 반복 import java.util.*; class Node { int data; Node lt, rt; public Node(int val) { data=val; lt=rt=null; } } public class Main { Node root; public void BFS(Node root) { Queue Q = new LinkedList(); //루트 노드는 넣어둔다. Q.offer(root); int L = 0; //맨 처음 루트 노트는 0 L은 레벨 while(!Q.isEmpty()) { int len = Q.size(); System.out.print(L + " : "); fo..

자연수 N이 주어지면 1부터 N까지의 원소를 갖는 집합의 부분집합을 모두 출력하는 프로그램을 작성하세요. 입력예제 3 출력예제 1 2 3 1 2 1 3 1 2 3 2 3 해당 숫자를 사용한다 / 사용하지 않는다. 로 2갈래의 트리가 그려지도록 구현해야한다. 숫자의 사용 여부를 체크해주는 배열이 필요하다. 맨처음은 다 사용하는거(1,2,3) 마지막은 다 사용하지 않는것(공집합) 매개변수로는 부분 집합의 종착점 레벨을 판단하고 사용할 숫자를 지정하는 L로 설정한다. public class Main { static int n; static int[] ch; public void DFS(int L) { //종착점(부분 집합) if(L==n+1) { String tmp = ""; for(int i = 1; i 0..

스택의 구조를 익히는데 좋음! 전위순회 - 부모 -> 왼쪽자식 -> 오른쪽자식 중위순회 - 왼쪽자식 -> 부모 -> 오른쪽자식 후위순회 - 왼쪽자식 -> 오른쪽자식 -> 부모 import java.util.*; class Node { int data; Node lt, rt; public Node(int val) { data=val; lt=rt=null; } } public class Main { Node root; public void DFS(Node root) { if(root==null) return; else { /* 전위 순회*/ //System.out.print(root.data + " "); DFS(root.lt); /* 중위 순회 */ //System.out.print(root.data + ..

피보나치 수열을 출력하시오. 입력은 피보나치 수열의 총 항의 수이다. 만약 7이 입력되면 1 1 2 3 5 8 13을 출력하면 된다. 왼쪽부터 뻗어나가서 차례로 중복인 값들은 뻗어나가지 않는다. 1 2에서 4로간 뒤 6으로 감. 1 1 2 3 5 8 13 을 출력해야한다. 1.fibo 배열없이 만들게 되면 DFS 메서드를 n만큼 10번 호출해야함. 2.fibo 배열을 만들게되면 DFS(10) 하나만 호출해도 fibo배열에 값이 모두 담기므로 한번 호출하고 배열 출력 3.이미 구한 값들을 다시 구하지 않게 하면 시간복잡도가 매우 좋아짐 fibo[n] > 0일 때 해당 값만 리턴 1.변수 이용 public class Main { public static void main(String[] args) { int..

import java.util.*; public class Main { public int count(int[] arr, int dist) { //말의 마릿수 int cnt = 1; //배치한 위치 int ep = arr[0]; for(int i = 1; i = dist) { cnt++; ep=arr[i]; } } return cnt; } public int solution(int n,int c, int[] arr) { int answer = 0; //mid를 가장 가까운 두 말의 거리로 배치시킨다. //더 좋은 답이 있다면 좁혀나간다. Arrays.sort(arr); int lt = 1; int rt = arr[n-1]; while(lt= ..

import java.util.*; class Main { static int n,m; public static void main(String[] args) { Scanner kb = new Scanner(System.in); n = kb.nextInt(); m = kb.nextInt(); int[] arr = new int[n]; for(int i = 0; i < n; i++) { arr[i] = kb.nextInt(); } System.out.println(solution(m, arr)); } //DVD의 최소용량크기를 결정해서 이분탐색하기 private static int solution(int m, int[] arr) { int answer = 0; //dvd가 9개일 때 최소 용량 크기는 9가 ..

import java.util.*; public class Main { public int solution(int n,int m, int[] arr) { int answer = 0; //이분검색은 무조건 정렬이 되어있어야한다. //(lt+rt) / 2 를 인덱스 값으로 따로 생성해두고 //해당 값이 큰지 작은지 보고 해당 인덱스 범위로만 탐색하면 된다. //검색 범위가 절반씩 줄어든다. //값이 없을 때도 있을 수 있으니 lt가 rt보다 커지면 멈춰야한다. Arrays.sort(arr); int lt = 0, rt = n-1; while(lt m) rt = mid - 1; //작은 쪽을 날리고 큰 쪽만 탐색 else lt = mid + 1; } return answer; } public static vo..