이진 탐색 트리 트리란? - 트리는 비선형 자료구조 중에서 자료들 간에 계층관계를 가진 계층형 자료구조다. - 트리를 구성하는 원소를 노드라고 하고 노드를 연견하는 선을 간선(edeg)이라 한다. - A에는 12개의 노드가 있다. - 트리 시작을 루트노드라 하고 레벨 0이 된다. - 같은 부모의 자식 노드들은 서로 형제노드 (Sibling Node)가 된다. - 자식노드들은 각각 독립하여 새로운 트리를 구성할 수 있으므로 각 노드는 자식노드 수만큼의 서브트리를 갖는다. - 한 노드가 가지는 서브 트리의 수, 즉 자식노드의 수를 그 노드의 차수(degree)라 한다. - 차수가 0인 노드 즉 자식이 없는 노드를 리프 노드(Leaf Node) 또는 단말 노드라 한다. - 여러 트리들의 집합을 포리스트라고 한다. 이진 탐색 .. Deque(Double-ended Queue) 데큐는 큐의 양쪽 끝에서 삽입과 삭제가 모두 발생할 수 있는 큐로서 스택의 설질과 큐의 성질 모두 가지고 있는 자료조 - 덱의 insertFront() 연산과 deleteFront()연산은 front를 스택에 top으로 생각했을 때 스택의 push()연산과, pop()연산과 같다. - 덱의 insertRear() 연산과deleteRear()연산은 rear를 스택에 top으로 각했을때 스택의 push()연산과, pop()연산과 같다. - 덱의 insertRear()연산과 deleteFront()연산은 일반 큐의 enQueue()연산, deQueue()연산과 같다. 연산 수행에 대한 덱의 상태 public class DQNode { char data; DQNode rlink; DQNode llink; }pu.. 연결큐 순차 자료구조 방식에는 몇가지 문제가 있다. - 사용 크기가 제한되어 있어서 큐의 길이를 마음대로 변경할 수 없다. - 원소가 없을 때에도 항상 처음 크기를 유지하고 있어야 하므로 메모리도 낭비 된다. 연결큐의 알고리즘 1. 공백 연결 큐 생성createLinkedQueue() fornt 원형 큐 선형 큐의 문제점 - rear가 배열의 마지막 위치에 있을때 앞에 빈자리가 있는 경우에도 포화 상태로 인식하고 삽입 연산을 하지 않는다. 큐의 빈자리를 사용하려면 앞으로 이동시켜 위치를 조정시켜야 하는데 복잡하여 큐의 효율성을 떨어뜨린다. 이런 문제를 해결하기 위해 원형 큐(Circular Queue)를 사용한다. 초기 공백 상태일때는 front와 rear 값이 0이 되고, 공백 상태와 포화 상태를 쉽게 구분하기 위해서 자리 하나를 항상 비워둠.원형큐의 공백 조건 상태는 front=rear가 된다rear는 앞으로 이동하면서 원소를 삽입하고 front는 rear가 이동한 방향으로 따라가면서 원소를 삭제배열의 인덱스가 n-1 다음에 다시 0이 되어야 하므로 사용할 다음 인덱스를 정하기 위해서 나머지 연산자 .. Queue는 무엇인가? - Queue는 '선입선출(first-in fisrt out) 자료구조를 구현한 자바 인터페이스이다. - java.util에서 제공 http://www.jroller.com/VelkaVrana/resource/java16collections/queues090524-final.pnghttp://www.jroller.com/velkaVrana/entry/java_1_6_collections_class - Iterable과 Collection의 기능을 가지고 있다는게 Queue의 특징 - Queue의 기능을 활용한 클래스 중 대표적인 클래스로 LinkedList가 있음@Test public void queueInsertion() { Queue queue = new LinkedList(); queue.add(".. 배열과 리스트 - 리스트는 특정 타입 값들이 순차적으로 정렬된 컬렉션이다. 자바에서는 LinkedList나 ArrayList 클래스를 일반적으로 사용 - 어떤 경우에는 LinkedList보다 ArrayList가 더 적합하며 반대일 수 도있다. - 사용하기 전에 리스트는 애플리케이션의 성능이나 메모리 사용량과 밀접한 관계가 있기 때문에 반드시 고민을 해봐야 한다. - 리스트를 사용하려면 메서드와 생성자 매개변수는 필드 정의로 List 인터페이스를 사용함.배열과 리스트의 관계public void arrayDefinitions() { int[] interger = new int[3]; boolean[] bools = {false, true, true, false}; String[] strings = new String[] .. 이진 검색 public static boolean binarySearch(List numbers, Integer value) { if (numbers == null ||numbers.isEmpty()) { return false; } Integer comparison = numbers.get(numbers.size() /2); if (value.equals(comparison)) { return true; } if (value < comparison) { return binarySearch(numbers.subList(0, numbers.size() / 2), value); } else { return binarySearch(numbers.subList(numbers.size() /2 + 1, numbers.siz.. 병합정렬 알고리즘 public static List mergesort(List values) { if (values.size() < 2) { return values; } List leftHalf = values.subList(0, values.size() /2); List rightHalf = values.subList(values.size() / 2, values.size()); return merge(mergesort(leftHalf), mergesort(rightHalf)); } private static List merge(List left, List right) { int leftPtr = 0; int rightPtr = 0; List merged = new ArrayList(left.size() + right.. 이전 1 ··· 4 5 6 7 8 9 10 ··· 12 다음