원형 큐를 사용하면서, 버퍼 1개를 빈 공간으로 사용하여 Empty와, Full 유무를 확인 하였습니다. Front : 값이 나올 인덱스 Rear : 값이 들어갈 인덱스 Full() : 큐가 가득 찬지 확인합니다. Empty() :: 큐가 비어 있는지 확인합니다. enqunue() : 값을 큐에 삽입합니다. dequeue(): 큐의 값을 한개 반환합니다. qPrint() : 남아있는 값을 출력합니다. Front == Rear 인 큐에 아무것도 없는 상태 Front == (Rear +1) % capactiy 인 큐가 가득 찬 상태 (Empty와 구분을 위하여 1개의 여분의 버퍼를 남겨둡니다) #include using namespace std; // Buffer을 한개 더 안 쓰는 Circular Queu..

push_front() : 앞에서부터 값을 넣는 기능 push_back() : 뒤에서부터 값을 넣는 기능 findNode() : 특정 값의 노드를 반환해주는 기능 addAfter() : 특정 노드의 뒤에, 값을 삽입해주는 기능 deleteAfter() : 특정 노드의 뒤에, 값을 삭제해주는 기능 lPrint(): 리스트의 전체 값을 출력해주는 기능 #include using namespace std; template struct Node { T data; Node* next; Node(const T& a, Node* n) : data(a), next(n) {} }; template class slist { private: Node* head; Node* current; public: slist() : h..

resize() : 사용할 수 있는 스택의 Capacity를 늘려주는 함수 push() : 스택에 저장 하는 기능 pop() : 스택에서 값이 빠져나오는 기능 top() : 스택의 맨 윗값을 출력하는 기능 capacity() : 스택의 용량을 출력하는 기능 size() : 스택의 크기를 출력하는 기능 empty() : 스택이 비었는지, 안 비었는지 유무를 출력하는 기능 #include using namespace std; template class mStack { private: T* arr; unsigned int m_capacity; unsigned int m_size; public: // 생성자 mStack() { m_capacity = 3; // default capacity 10; m_size ..

⭐ 기수정렬 (Radix Sort) 계수정렬(Counting Sort)를 이용한 정렬입니다. 기수정렬을 하려면, 자리 수 별로 계수 정렬을 실행하면 되는 정렬 방법입니다. 각 자리 수의 값을 기준으로, stable한 계수 정렬을 통하여 정렬해줄 수 있습니다. 계수정렬의 자세한 내용은 계수정렬을 클릭하여 확인 해 보시면 좋을 듯 합니다. #include #include using namespace std; void countingSort(int nums[], int length, int radix) { int* SortedArr = new int[length]; int* count = new int[10] {0, }; int* acc_count = new int[10] {0, }; int div = pow..

⭐ 힙 정렬 (Heap Sort) 우선 힙이란 자료구조에 알고 있다고 가정하고, 진행하겠습니다. 진행과정 1. 정렬하고 싶은 배열을, heapify를 시켜줘서, MaxHeap을 만듭니다. 2. Heap의 0번째 노드인 Max값을 정렬된 배열의 마지막 인덱스에 저장해줍니다. 3. Heap의 0번째 노드에, 끝의 노드를 복사해줍니다. 4. Heap의 length - 1 값을 대상으로 다시 heapify 해줍니다. 5. 2번과정의 마지막 인덱스-1 을 대상으로 복사 시켜주며 2~4 과정을 반복해줍니다. #include using namespace std; void swap(int nums[], int length, int rootIdx) { int largeIdx = rootIdx; int leftChild ..

⭐ 주제 만약 숫자를 정렬하고 싶다고 했을 때, 그 숫자의 범위를 알고 있다면, counting 을 하여 정렬을 할 수 있습니다. 숫자의 범위가 0이상의 정수인 k까지 일 때, 정렬하고 싶은 arr를 돌면서 숫자가 몇번 출현 했는지를 보고 그 수의 인덱스의 count를 1씩 올려줍니다. 인덱스가 올라갔으면 인덱스를 가지고 0부터 k까지 count를 더해주어 각 숫자에 대한 인덱스를 알 수 있께 해줍니다. 이 후 정렬을 해야할 배열의 끝부터 0까지 인덱스를 찾아가면서 정렬을 해주면 됩니다. #include using namespace std; // O(n + k) void countingSort(int nums[], int length, int size) { int* SortedArr = new int[l..

⭐ 합병 정렬 (Merge Sort) 크게 나누는 Split부분 합치는 merge 부분이 있습니다. split 부분에서는 재귀적(reculsive) 방법을 이용하여 나눠진 개수가 1개가 될 때 까지 나눠줍니다. 이 후, begin Index와 last Index를 이용하여, merge를 해줍니다. 각각 비교를 해가며, 작은 수 부터 vector에 임시 저장한 후 반복문이 끝난 후 그 임시저장 한 vector를 다시 배열에 재배치 시켜줍니다. 이를 반복하면 정렬이 완성이 됩니다. #include #include using namespace std; void mergeSort(int nums[], int beginIdx, int lastIdx) { // O(nlgn) vector tmp; if (beginI..

⭐ 퀵 정렬 (Quick Sort) 하나의 기준이 되는 인덱스를 랜덤으로 Pivot으로 설정하고, 그 값을 끝 값과 바꿔준 뒤 맨 끝값을 제외한 왼쪽와 오른쪽(맨 끝값 -1)을 대상으로 왼쪽은 배열[Pivot]값보다 작은 값 오른쪽은 배열[Pivot] 값보다 큰값으로 파티셔닝과 스왑을 통하여 정렬을 해줍니다. #include #include using namespace std; int RangeRandom(int range_min, int range_max) { int u = (double)rand() / (RAND_MAX + 1) * (range_max - range_min) + range_min; return u; } void quickSort(int nums[], int beginIdx, int l..