후로링의 프로그래밍 이야기

비교기반의 정렬알고리즘은 어떤 경우에도 O(n logn)보다 빠를 수 없습니다. 이를 증명하하는것으로 Sorting 부분은 넘어가도록 하겠습니다. Insertion Sort, Heap Sort, Quick Sort, Counting Sort, Radix Sort, Bucket Sort등등은 인터넷상에 자료가 많습니다. 혹시라도 잘 모르시는분들은 찾아서 해보시면 되겠습니다. Sort가 진행되는 과정은 Decision Tree로 나타낼 수 있습니다. 증명에는 몇가지 Lemma(참으로 증명된 정리)가 필요합니다. 1. 모든 정렬 알고리즘의 decision tree는 n!개의 Permutation(순열)을 가진다. (다시말해, 정렬이 될 수 있는 모든 경우의 수가 n!이란 뜻입니다. ) 2. Binary tre..

Binomial Heap을 배우기 위해서 Binomial Tree가 어떤 것인지 부터 알아보겠습니다. Binomial Tree Binomial Tree는 우선순위 큐 형태의 자료구조입니다. 아래 그림과 같이 한 Tree의 루트 노드가 다른 루트 노드를 가리키는 형태입니다. 노드의 수는 2^k(루트에 새로 붙여지는 트리와 붙는 트리의 크기가 같다), 루트에 붇기 때문에 높이는 1씩 증가하게되며 트리의 깊이는 K combination i(K에서 i를 뽑는 경우의수), 그리고 루트의 degree가 가장 크게 됩니다. Binomial Heap Binomial Heap의 각각의 Binomial Tree는 min-heap입니다. 그리고 k값이 같은 Binomial Tree는 존재하지 않습니다(차수가 같은 트리가 존..

Heap은 기초적인 내용이지만 Binomial Heap을 다루기 위해 내용을 확실히 숙지해야 하므로 설명하고 넘어가도록 하겠습니다. Heap 이란? 다음 조건을 만족하는 key값을 저장한 Binary Tree 입니다. 1. Heap-Order : 모든 노드는 자신의 부모노드보다 작거나 큰 값을 가진다. 2. Complete Binary Tree : 항상 왼쪽부터 꽉 채워져 있는 형태의 Binary Tree여야 한다. Heap과 Priority Queues(우선순위 큐) 우리는 힙을 우선순위 큐, 다시말해 우선순위가 높은것을 먼저 나가게 하는데에 쓸 수 있습니다. Min heap은 key값을 오름차순 정렬 하는데 쓰일 수 있습니다. Heap에서의 Insert 힙에서의 구조적 조건과 순서적 조건을 맞춰주면 ..

Data structure 자체가 알고리즘을 구현하는 방법이 될 수 있습니다. Skip List 정렬된 linked list에 대해 적용하는 알고리즘으로 빠른 검색및 삽입 삭제를 가능하게 해주는 자료구조입니다. Skip List는 key와 element쌍으로 되어있는 리스트가 여러 레이어에 걸쳐 있는 형태입니다. 각 레이어는 플러스 무한대와 마이너스 무한대를 항상 키 값으로 가지고있고 가장 하위 레이어인 S0는 오름차순으로 정렬되어 있습니다. 그리고 하위레이어는 상위 레이어를 포함하는 형태입니다. 그림으로 살펴보면 아래 그림과 같습니다. Skip List에서의 Search Skip List에서의 Search는 최상단 list의 첫번째 위치에서부터 시작합니다. 만약 현재 위치의 다음 element가 찾으려..

알고리즘에 대해 공부 및 정리를 하며 포스팅을 하려 합니다. 일반적으로 학부때 배우는 간단한 알고리즘이 아닌 Advanced한 부분에 대한 걸 다루려 하니 많은 관심 부탁드립니다. 기본적으로 Introduction to Algorithms 3rd edition을 참고하여 작성하게 될 것입니다. 정렬, Dynamic Programming, Greedy Algorithms등등 을 하고 NP-Complete까지 다뤄볼 작정입니다. 먼저 알고리즘에 대해 간단히 정의하고 알고리즘에 쓰이는 자료구조에 대해 설명하도록 하겠습니다. 컴퓨터 공학에서의 알고리즘이란? "문제를 푸는 잘 정의된 과정"입니다. 어떤 미사여구나 수식어구도 필요없이 위 정의만으로도 컴팩트 하게 알고리즘을 정의 할 수 있습니다. 컴퓨터 공학전공이거..