STUDY/자료구조 (6) 썸네일형 리스트형 [자료구조] stack, queue, sorted list, unsorted list MergeList -> 배열 기반 Sorted -> list1 과 list2를 합쳐서 result로 반환 -> big o: O(N^2) Sorted List 1. 클라이언트 함수: 배열, 링크드 리스트 모두 같은 구현 void MergeList(SortedType list1, SortedType list2, SortedType& result) { result = list1; ItemType it; list2.ResetList(); for (int i = 0; i < list2.LengthIs(); i++) { list2.GetNextItem(it); result.InsertItem(it); } } template void MergeLists(SortedType& l_a, SortedType& l_b, S.. [자료구조] stack, queue, 정렬&비정렬 리스트 시간복잡도 정리 시간복잡도와 공간복잡도 알고리즘을 평가할 때는 두가지 요소로 측정한다. 첫째는 시간복잡도, 둘째는 공간복잡도 시간 복잡도는 말 그대로 알고리즘을 수행하는데 걸리는 시간이다. 즉, 수행시간이다. 공간 복잡도는 알고리즘의 메모리 사용량을 말한다. 알고리즘을 평가할 때 고려해야할 점은 알고리즘이 최악의 경우로 돌아가게 되는 것을 기준으로 해야한다는 것이다. 그 이유는 worst case를 사용해야 다른 요소들이 순수한 알고리즘만 평가하는 데 방해를 하지 않기 때문이다. 예를 들어, 리스트에서 해당되는 값을 찾아내는 알고리즘이라고 하자. 이럴 경우 찾으려는 아이템이 리스트의 첫번째에 위치하는 경우면 바로 찾을 수 있고 시간도 절약되니까 좋겠지만, 아이템이 리스트의 어느 위치에 있을지는 아무도 모르기 때문에 평가.. [자료구조] 정렬 리스트 Array based vs Linked List 정렬 리스트 데이터가 특정 기준으로 정렬되어있는 리스트이다. 예를 들면 정수형 리스트인 경우 오름차순 or 내림차순으로 정렬되어 있다면 정렬리스트이다. 정렬이 되어 있기 때문에 시간복잡도면에서 비정렬 리스트보다 효율적이다. 예를 들어 리스트에서 아이템을 찾아주는 함수의 시간복잡도를 살펴보자면 정렬 리스트가 binary search로 구현된 경우, 시간 복잡도는 O(logN)이지만 비정렬 리스트는 시간 복잡도가 O(N)이다. search 함수 정렬 리스트 (2진 탐색) 비정렬 리스트 시간 복잡도 O(logN) O(N) 정렬리스트를 구현하는 방식도 다양하다. 일단 여기서는 2진 탐색을 기준으로 설명하겠다. Binary Search (2진 탐색) 2진 탐색은 정렬이 된 자료를 반으로 나누어 가며 검색을 하는 .. [자료구조] 비정렬 리스트 Array based vs Linked List 비정렬 리스트 비정렬 리스트는 말 그대로 리스트가 정렬되지 않는 상태로, 그냥 들어가면 들어가는대로 저장되는 자료구조이다. 쉽기 때문에 나머지 설명은 생략하고 구현 설명에 좀 더 초점을 두겠다. Array based implement class unsorted { public: unsorted(); void get(int &item); //currentpos에 있는 데이터를 돌려줌 void reset(); // currentpos를 초기화 시킴 void insert(int item); void deleted(int item); int length(); bool full() const; void retrieve(int& item, bool& find); // 아이템이 리스트에 있는지 확인 private: .. [자료구조] Queue - Array based vs Linked List Queue What is Queue? 큐(queue)는 스택과 달리 데이터를 줄 세우는 것이다. 즉 먼저 들어간 데이터가 먼저 나오는 형태의 선형자료구조를 말한다. queue의 특징 먼저 들어간 데이터가 가장 먼저 나오게 된다 -> FIFO라고 함( First In First Out ) 가장 앞에 위치한 데이터를 가리키는 front와 맨 뒤에 위치한 데이터를 가리키는 rear 두개의 변수가 필요하다. queue class Array Based vs Linked List 저번 stack의 내용과 비슷하게 배열과 LL 두가지 선형구조로 구현할 수 있다. queue 구현의 포인트는 데이터가 full인지 empty인지 구별하는 것이다. 그냥 구현을 하게 되면 rear+1=front 이 의미하는 바가 full인지.. [자료구조] stack- Array based vs Linked List stack what is stack? stack은 말 그대로 데이터를 쌓아올리는 형태의 자료구조를 말한다. 접시 100장을 차례대로 쌓거나 책을 쌓는 것 등등으로 이해 가능. 선형구조로 배열, 연결리스트로 구현 가능하다. stack의 특징 마지막으로 추가되는 자료가 가장 먼저 나오는 특성을 가진다 -> LIFO라고도 함 (Last In First Out) 접시 100장을 쌓으면 맨 밑에 있는 접시를 가장 안전하게 뺄 수 있는 방법은 위에서 부터 차례대로 빼서 맨 밑의 접시에 도달하는 방법 밖에 없음 top 지시자에 한해서만 데이터에 접근 가능 (push, pop 함수 모두) stack class Array based vs Linked LIst stack에서 데이터를 쌓을 때 두가지 형태로 쌓을 수 있다... 이전 1 다음
