공부기록

Queue? 구현 queue에서 구현해야 하는 기능은 아래의 인터페이스와 같다. public interface Queue { int size(); boolean isEmpty(); void enqueue(E e); E first(); E dequeue(); } queue를 구현하는 방법에는 배열을 사용하는 방법, linked list를 사용하는 방법이 있다. 배열을 사용한 Queue, Array Queue public class ArrayQueue implements Queue { private E[] data; private int f = 0; private int sz = 0; public ArrayQueue(){ this(CAPACITY); } public ArrayQueue(int capacity..

Linked List? 구현 public class SinglyLinkedList { private static class Node{ private E element; private Node next; public Node(E e, Node n){ element = e; next = n; } public E getElement(){ return element; } public Node getNext(){ return next; } public void setNext(Node n){ next = n; } } private Node head = null; private Node tail = null; private int size = 0; public SinglyLinkedList(){} public int..

Stack? 구현 먼저 stack에서 구현해야 하는 기능은 다음과 같다. public interface Stack { int size(); boolean isEmpty(); void push(E e); E top(); E pop(); } stack을 구현하는 방법은 배열을 사용하는 방법과 linked list를 사용하는 방법이 있다. 배열을 사용한 Stack, ArrayStack 배열을 사용하여 구현한 stack을 ArrayStack이라 칭한다. 구현한 코드는 아래와 같다. public class ArrayStack implements Stack{ public static final int CAPACITY = 1000; private E[] data; private int t = -1; public Ar..

문제 https://leetcode.com/problems/next-permutation/

JVM? Java Virtual Machine (이하 JVM)은 추상적인 컴퓨팅 머신이다. JVM은 Java 컴파일러에 의해 생성된 바이트코드를 기계어로 바꾸어주는 역할을 한다. JVM은 java로 작성된 프로그램에게 그들을 실행시키기 위한 프로그램으로 보여지게 된다. 때문에, java 프로그램들은 동일한 인터페이스와 라이브러리를 가지고 작성될 수 있게 된다. JVM은 특정한 OS에 호환되도록 만들어져서, Java 프로그램을 해당 OS에서 돌아가도록 만든다. 이러한 식으로 Java 프로그램은 플랫폼 독립성을 띄게 된다. 다만 JVM 자체는 플랫폼 종속적인 특성을 띈다. 자바 실행 과정 작성된 자바 코드는 Java Compiler 에 의해 바이트코드로 변환된다. Class Loader는 이 변환된 바이트코..

Hashing? key 값에 hash function을 적용하여 hash table의 주소 (entry index)를 산출하여 데이터를 탐색하는 것을 hashing이라고 한다. 데이터를 담은 자료구조를 모두 탐색하는 것이 아닌 키 값을 통해 빠르게 탐색하기 위해 사용한다. O(1)의 복잡도를 기대할 수 있다. hash에서 value를 담는 자료구조를 table이라고 하고 table에 대한 CRUD는 key에 의해 관리된다. hash(key)해서 나온 값이 곧 table의 인덱스이고, 인덱스에 대응하는 entry에 필요한 정보를 저장하게 된다. 당연한 이야기지만, table은 인덱스에 대해 정렬되어 있다. Collision key값에 hash function을 적용하여 주소값을 산출하다 보면 같은 key가..

Heap? 트리 안에 있는 원소들이 서로 비교될 수 있는 이진트리이다. 힙은 다음과 같은 두 가지 규칙이 있는 이진트리이다. 각 노드의 값은 그 노드의 자식들의 값보다 같거나 크다. (max heap의 경우) 이 트리는 complete binary tree (완전 이진 트리) 이므로 가장 깊은 노드들을 제외한 나머지 노드들은 가능한 한 많은 자식들을 가져야 한다. heap의 각 노드는 우선순위를 가진 원소를 하나 포함한다. heap의 규칙은 다음과 같다. 각 노드의 원소는 자식 노드의 원소에 대해 같거나 더 높은 우선순위를 가진다. 이 트리는 완전이진트리이다. Operations adding Reheapification upward의 성격을 가진다. 절차는 아래와 같다. 새로운 원소를 heap의 가능한 ..

선형, 비선형 자료구조 array, list, stack, queue는 모두 선형자료구조이고 graph, tree는 비선형 자료구조이다. Binary Tree? 먼저, 최대 2개의 자식노드를 가질 수 있는 노드들로 이루어진 트리를 이진트리라고 한다. 이진트리의 종류에는 아래와 같은 것이 있다. full binary tree 모든 leaf node가 같은 깊이를 가지고, 모든 non leaf node들은 2개의 자식을 가지는 트리 complete binray tree 가장 깊은 노드를 제외한 노드들은 가능한한 많은 자식을 가져야하고, 가장 깊은 레벨에서 모든 노드들은 왼쪽부터 채워져 있어야한다. Tree의 구현체 배열과 노드로 표현할 수 있다. 배열에서 root를 0 번지부터 시작하면 left child ..