자료구조와 알고리즘 (6) 썸네일형 리스트형 힙 힙은 이진 트리다. 이진 탐색 트리와는 다르게, 왼쪽부터 채워넣는다. 즉 sibling 간의 크기는 별로 상관 있지 않다. 대신 부모와 자식 관계에선 크기가 상관 있다. 힙 또한 매우 복잡해서, 일단 계속 진도를 나간다음에 다시 정리해보도록 하겠다. 트리 가장 대표적인 트리는 이진 트리다. 이진 트리를 사용할 경우 탐색 시간이 매우 적게 소요된다. (O(log n) ) 그러나 비대칭적으로 자료가 정리되어 있으면 배열과 다를 바 없다. 트리는 너무 복잡해서 다음에 한번 더 들으면서 더 제대로 정리해보려고 한다. 실제로 구현할 때도 매우 어려웠다. hash table hash table은 배열을 바탕으로 한 자료구조다. 삽입 및 검색을 할 때 매우 빠른 속도로 처리한다. 그러나 배열을 기반으로 했기 때문에, 크기가 제한되어 있다. hash function을 사용하여, 각 key들에 index를 부여한다. 이러한 index가 있기에, 각 key에 빨리 접근하여 value를 가져올 수 있다. 그러나 index 번호가 겹칠 경우 충돌이 일어날 수 있다. 이러한 충돌을 방지하기 위한 방법 중 유명한 방법은 chaining과 linear probing이다. Chaining은 linkedlist와 결합하여 사용하는 방식으로, 다른 value를 가진 key 가 동일한 index 번호를 갖게 될 경우, linkedlist 처럼 포인터를 사용해서, head에 새로운 값을 넣는 방식이.. Stack Stack은 queue와 반대로 LIFO 구조다. 즉 마지막에 들어온게 제일 먼저 나간다. Stack 클래스는 Vector 클래스를 확장하고, Collection, List와 같은 인터페이스들을 구현한다. Stack의 주요 메소드는 push()와 pop()이다. Stack의 장점 - 구현이 쉽다 - 데이터 저장 및 읽기 속도가 빠르다 Stack의 단점 - 데이터 크기를 미리 정해야 한다. public class MakeQueue { public static void main(String[] args) { Stack a = new Stack(); System.out.println(a.isEmpty()); a.push("Hi"); System.out.println(a.peek()); a.pop(); try{.. Queue 큐는 FIFO다. 먼저 들어오면 먼저 나간다. 음식점에 대기줄을 생각해보면 된다. 먼저 줄에 있는 사람이 먼저 들어갈 수 있다. 자바에서 Queue는 Collection를 확장한 interface 다. Queue를 구현한 대표적인 클래스에는 LinkedList가 있다. Queue에 정의되어 있는 메소드는 요소를 추가하는 offer(e), 맨 앞에 있는 요소를 제거하는 poll(), 맨 앞에 있는 요소를 보는 peek()가 있다. import java.util.*; //enqueue와 dequeue, peek 구현해보기 public class MakeQueue { private ArrayList a = new ArrayList(); public Queue b = new LinkedList(); public.. Arrays (배열) 배열은 객체를 저장하는 상자다. 저장되어지는 객체는 동일한 타입을 가지고 있어야 하고, 배열의 크기는 생성 전에 정해지고, 그 크기는 변하지 않는다. 각 객체는 배열의 요소가 되고, 0부터 시작하는 index 번호를 갖게 된다. 배열 선언하기 배열을 선언하는 것은 단순히 컴파일러에게 어떤 타입의 객체들을 이 변수에 저장할 것이라고 알려주는 것이다. 실제로 객체를 생성하려면 초기화를 해주어야 한다. public class Practice { public static void main(String[] args) { int[] arr; // arr이라는 배열에 int 타입의 객체들을 담을 것이다. //이 상태로 실행하면 java: variable arr might not have been initialized.. 이전 1 다음
