기주

B-tree 알아보기이진탐색트리(BST)-각 노드는 최대 2개의 자녀 노드를 가진다.-모든 노드의 왼쪽 서브 트리는 부모보다 작은 값들만 가지고 모든 노드의 오른쪽 서브 트리는 부모보다 큰 값을 가진다.-삽입,검색,삭제의 평균적인 시간복잡도: O(logN)-하지만 편향된 트리가되면 최악의 경우 O(N)까지 떨어질 수 있다 이진 탐색트리의 문제점-깊이가 깊어지면 검색, 삽입성능이 떨어진다.-균형유지가 어렵다.    자녀노드를 더 많이 갖기위해서는 어떻게 해야하는가?-> 상위 노드에 더 많은 키값을 가지면 된다.예를들어 자녀 노드를 3개씩 갖기위해서는 부모 노드에 2개의 키값을 가져야한다. 2개의 키 값이 있다면 3가지 값의 범위를 만들어 낼 수 있기 때문. ( k2)왼쪽자식: 작은 키값보다 작은값중간자식:..

이진트리탐색 구현하기- BFS(너비우선탐색)  BFS(너비우선탐색)-bfs는 트리의 각 레벨을 순차적으로 탐색하는 방법이다.  코드Node 클래스 생성각 node는 값, 왼쪽자식, 오른쪽자식으로 구성되어있음.이진트리탐색(BFS)bfs를 구현하기위해서는 큐를 이용해야 한다.여기서는 덱을 이용해서 구현했다. class Node { int data; Node lt,rt; public Node(int val) { data = val; lt=rt=null; }}public class Main { static Node root; public static void BFS(Node root){ Deque dq = new ArrayDeque(); ..

이진트리탐색 구현하기- DFS(깊이우선탐색)   코드Node 클래스 생성각 node는 값, 왼쪽자식, 오른쪽자식으로 구성되어있음.이진트리탐색(DFS)출력문의 위치에 따라 전위우선탐색, 중위우선탐색, 후위우선탐색으로 바뀔 수 있음. class Node { int data; Node lt,rt; public Node(int val) { data = val; lt=rt=null; }}static Node root;public static void DFS(Node root){ if(root==null) return; else{ System.out.print(root.data + " "); DFS(root.lt); D..

전역변수n : 집합의 개수전역변수 ch: 하나의 부분집합 상태( 해당 숫자의 인덱스가 1이면포함, 0이면 비포함.)ch[L] = 1: L숫자 포함ch[L] = 0: L숫자 비포함static int n; // 전역변수: 집합의 개수static int[] ch; // 전역변수: 하나의 부분집합 상태( 해당 숫자의 인덱스가 1이면포함, 0이면 비포함.)public static void DFS(int L){ if(L==n+1){ String tmp = ""; for(int i=1; i0) System.out.println(tmp); // 부분집합이 공집합이아니라면 출력. } else { ch[L]=1; DFS(L+1); ch[L]=0..

[알고리즘] 재귀함수 활용해보기 -재귀함수의 특성함수가 자기 자신을 호출한다함수호출시 스택프레임이 생성되어 스택에 담긴다.(모든 함수의 특성) 재귀함수는 그 특성을 이해하면 다양한 방식으로 활용할 수 있다.하지만 성능이 반복문보다 떨어지기에 제한적으로 사용해야한다. 재귀함수는 자신을 호출하는 함수기 때문에 기본적으로 이를 멈추기위한 방법이 있어야함. 안그럼 무한히 호출된다. 기본적인 틀은 비슷하기때문에 외워두는 것이 좋다.     1.  오름차순 수열 출력해보기재귀함수를 활용해서1 2 3 4 5 6 7 8 9 10.. 이런식으로 오름차순으로 출력해보기public static void DFS_desc(int n){ // 내림차순 출력하는 재귀함수 if(n==0) return; else{ ..

10. 마구간 정하기(결정알고리즘) 설명N개의 마구간이 수직선상에 있습니다. 각 마구간은 x1, x2, x3, ......, xN의 좌표를 가지며, 마구간간에 좌표가 중복되는 일은 없습니다.현수는 C마리의 말을 가지고 있는데, 이 말들은 서로 가까이 있는 것을 좋아하지 않습니다. 각 마구간에는 한 마리의 말만 넣을 수 있고,가장 가까운 두 말의 거리가 최대가 되게 말을 마구간에 배치하고 싶습니다.C마리의 말을 N개의 마구간에 배치했을 때 가장 가까운 두 말의 거리가 최대가 되는 그 최대값을 출력하는 프로그램을 작성하세요.입력첫 줄에 자연수 N(3둘째 줄에 마구간의 좌표 xi(0출력첫 줄에 가장 가까운 두 말의 최대 거리를 출력하세요.예시 입력 1 5 31 2 8 4 9예시 출력 13    풀이전략1. 이..