공부기록

red-black tree? 가장 유명하고 많이 사용되는 균형이진 트리이다. 즉 모든 연산의 시간복잡도가 _O(log N)_임을 보장한다. 노드가 red, black 색상을 가지며 아무것도 없는 nil을 leaf 노드라고 생각한다. red-black tree는 다음 5가지 조건을 만족해야 한다. 모든 노드는 red, black의 색을 가진다. root 노드는 black이다. leaf 노드는 black이어야 한다. red 노드는 두 개의 자식을 가지며, red 노드의 child 노드는 색이 모두 black이어야 한다. black 노드의 자식은 어떠한 색을 가지든 상관이 없다. *tree의 전체 depth가 log N 이기 위해서, 각 노드에서 leaf 노드로 가는 경로들 중에 있는 블랙노드의 개수는 항상 ..

Linked List? 구현 python으로 구현한 코드는 아래와 같다. class Node(): def __init__(self, data, nextNode = None): self.data = data if nextNode == None or type(nextNode) == Node: self.nextNode = nextNode else: print("__init__ node type error :", type(Node)) def getData(self): return self.data def setData(self, val): self.data = val def getNextNode(self): return self.nextNode def setNextNode(self, node): if type(..

Sorting O(nlogn)의 복잡도를 가지는 정렬 알고리즘들에는 대표적으로 merge sort, quick sort, heap sort 가 있다. 이번 포스팅에서는 이 알고리즘들에 대해서 공부한다. Merge Sort 구현된 코드는 아래와 같다. public class MergeSort { void merge(int arr[], int l, int m, int r){ int n1 = m - l + 1; int n2 = r - m; int L[] = new int[n1]; int R[] = new int[n2]; for(int i=0; i arr[largest]) largest = r; if(largest != i){ int swap = arr[i]; arr[i] = arr[largest]; arr[l..

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..

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의 가능한 ..