DataStructure
-
[ Open Data Structures ] - Asymptotic NotationDataStructure 2021. 5. 5. 21:07
Asymptotic Notation 자료구조를 분석함에 있어서 다양한 작업(Operation)들의 Running time에 대해 논할 때가 있다. 당연히 정확한 Running time은 각각 컴퓨터에 따라 다르게 나타난다. 우리가 어떤 Operation의 Running time에 대해 이야기 할 때는 Operation 도중에 수행되는 컴퓨터의 지시(Computer instructions)의 수를 이르는 것이다. 아주 간단한 코드에서도 이 양[量]은 정확하게 계산해내기 힘들다. 따라서 Running time을 정확하게 계산하는 대신에 우리는 소위 말하는 Big-Oh notation을 사용하기로 한다. 어떤 함수 f(n)에 대해서 O(f(n))은 다음과 같은 함수의 집합을 이르는 것이다. 도표로 생각을 해보..
-
[ Open Data Structures ] - DoublyLinkedList - 2DataStructure 2021. 4. 14. 22:31
Summary 다음과 같은 Theorem이 Doubly Linked List의 성질 혹은 Perfomance를 정리한다. Theorem. DLList는 List Interface를 구현할 수 있다. 이 Implementation에서 Add, Remove, Set, Get은 모두 O(1 + min{i, n - i})의 Running time을 갖는다. DLList에서 GetNode의 시간복잡도를 무시한다면 모든 작업이 상수시간 내에 해결된다는 것을 주목할 필요가 있다. 즉, 오직 특정 Node를 찾는 작업만이 시간을 많이 잡아먹고 한 번 Node를 잡으면 어떤 작업도 상수시간 내에 해결할 수 있다. 이것이 Array-Based List와 가장 큰 차이를 나타내는 지점이다. Array-Based List는 ..
-
[ Open DataStructures ] - Doubly Linked List - 1DataStructure 2021. 4. 14. 22:13
Doubly Linked List(以下DLList)는 Singly Linked List와 유사한 형태이다. 차이점이라고 하면 SLList는 Node u가 존재할 때, u->next에 해당하는 정보만을 가지고 있으나 DLList는 Node u에 선행하는 Node w를 가리키는 Pointer혹은 Refernce (u->prev)를 가지고 있다는 점이다. Doubly Linked List SLList를 구현함에 있어서 특별히 주의를 기울여야만 했던 요소들이 있었다. 가령 List끝(tail)의 정보를 제거하는 경우나 크기가 0인(n=0)경우에 Add 작업을 수행하는 경우가 있다. DLList는 이렇게 주의를 기울여야 하는 요소가 더욱 늘어난다. 다양한 상황에 적합하게 대응할 수 있는 방법 중 하나가 Dummy..
-
[ Open DataStructures ] - The InterfaceDataStructure 2021. 4. 9. 22:58
The Interface 자료구조를 배우는데 있어서 Interface와 Interface의 Implemetation을 구분하는 것은 매우 중요하다. Interface는 データ構造가 무엇을 하는지 묘사하는 것에 가깝고 자료구조의 Implementations는 실제 データ構造가 행하는 그 무엇을 어떻게 수행하는지 묘사되어 있는 것에 가깝다. An Interface는 종종 Abstract Data Type이라도고 불리는데 이는 자료구조가 제공하는 Operation(혹은 関数나 作業)을 정의하고 해당 Operation의 Semantics나 의미 등을 정의한다. Interface는 자료구조가 어떻게 operations을 implement하는지 알려주지 않는다. 오직 Interface가 가진 Operation의 목..
-
[ Open Data Structures ] - Singly Linked List - 1DataStructure 2021. 4. 9. 17:28
Array가 아닌 Pointer를 기반으로 list interface를 공부해 보도록 합시다. 여기서 구조는 List Item을 포함하는 노드[Node]로 이루어져 있습니다. 포인터를 이용한 이 노드들은 일련의 연속적인 연결체로서 존재하게 됩니다. 우리는 먼저 FILO Interface ( Stack )와 Queue Operation들을 상수 시간 내에 해결해주는 Singly Linked List ( 以下SLL )를 공부하고 Deque Operation들을 상수 시간 내에 해결해주는 Doubly Linked List에 대해서 공부하기로 합니다. SLL은 Array-Based List Interface와 비교해서 확연한 장단점이 존재합니다. 가장 눈에 띄는 단점은 상수 시간 내에 임의의 자료에 접근하는 S..
-
[ Open Data Structures ] - Rootish Array Stack - 1DataStructure 2021. 3. 6. 16:04
Rootish Array Stack Get and Set 이러한 방법을 토대로 Get과 Set을 직관적으로 작성할 수 있다. 가장 먼저 적절한 block b를 찾아내고 해당 block 내의 index i가 위치할 index j를 계산하면 된다. 마지막으로 호출한 각 함수마다 적절한 조치를 취하면 끝이다. 일반적으로 이 작업들은 Constant time내에 완료된다. Add and Remove Grow()에서 소모하는 시간을 제외하면 Add의 Running time은 Array Stack처럼 원소들의 위치를 교환하는 작업에 압도적으로 의존하게 된다. 따라서 Array Stack과 같은 O(1 + n - i )의 Running time을 갖는다. Remove는 Add와 비슷하게 동작한다. i+1, i+2, ..
-
[ Open Data Structures ] - Dual Array Deque - 1DataStructure 2021. 3. 4. 14:34
Dual Array Deque : Building a Deque From Two Stacks /* 수정 : Balance() 함수의 back stack을 확장하는데 있어서 For-Loop에 Get(nb + j )를 Get(nf + j)로 수정 */ Dual Array Deque를 만들어 본다. Array Stack을 두 개 사용해서 전에 만들었던 Array Deque와 비슷한 성능을 낼 수 있다. 사실, Asymptotic performance자체는 Array deque와 크게 차이가 나지 않지만, 두 개의 간단한 자료구조를 조합하여 정교한 자료구조를 만드는 좋은 예제가 될 수 있다. Dual Array Deque는 두 개의 Array Stack을 사용하는 List를 나타낸다. Array Stack이 배..
-
[ Open Data Structures ] - Array Deque - 1DataStructure 2021. 2. 28. 16:41
Array Deque : Fast Deque Operation using an array Array Queue는 배열의 한 지점에서 정보를 저장하고 반대편에서 삭제하는 자료구조였다. Array Deque는 양지점 어느 쪽에서든 자료의 저장/삭제를 효율적으로 할 수 있도록 해준다. 이 자료구조는 Array Queue에서 봤던 Circular array를 사용하여 List interface를 implement한다. 각 변수가 의미하는 바는 Array Queue와 크게 다르지 않다. 삭제할 index를 추적하는 mElem2Remove, 배열에 저장된 원소의 개수를 추적하는 mNumOfElem, 그리고 배열 mArr. Get(_i) Set(_i, _x) Get(_i)과 Set(_i, _x)의 operation은..