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

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까지 다뤄볼 작정입니다. 먼저 알고리즘에 대해 간단히 정의하고 알고리즘에 쓰이는 자료구조에 대해 설명하도록 하겠습니다. 컴퓨터 공학에서의 알고리즘이란? "문제를 푸는 잘 정의된 과정"입니다. 어떤 미사여구나 수식어구도 필요없이 위 정의만으로도 컴팩트 하게 알고리즘을 정의 할 수 있습니다. 컴퓨터 공학전공이거..