* 퀵 정렬 이론과 예시를 토대로 구현 * 여기서 나온 과정과 약간 다르게 구현함 https://hyrule.tistory.com/63 220420_정렬_퀵 정렬(Quick Sort) 이론 hyrule.tistory.com //QuickSort.h /* * 비대칭 정렬 * 최선의 경우에는 가장 빠른 성능을 가지지만 * 최악의 경우에는 매우 느리다. * 과정 요약 7 9 5 1 3 6 4 Pivot(중심점)을 하나 정함 -> (일반적으로 맨 앞 자리)7 Pivot보다 작은 건 왼쪽, Pivot보다 큰 건 오른쪽 Pivot: 7 5 1 3 6 4 7 9 * Pivot 7 기준 왼쪽 배열부터 정렬(1, 3, 4, 5, 6만 놓고 정렬) 다시 Pivot 설정 -> 5(맨 앞자리) 1 3 4 5 6 7 9 다시 ..
* 처리 과정을 바탕으로 구현해 보았음 https://hyrule.tistory.com/61 220420_정렬_힙 정렬(Heap Sort) 처리 과정 hyrule.tistory.com //HeapSort.h /* * 힙정렬은 최대힙과 최소힙이 있다. - 최대힙으로 정렬하면 내림차순, 최소힙으로 정렬하면 오름차순으로 정렬됨. - 최대힙 -> 높은 수를 위로 - 최소힙 - > 낮은 수를 위로 * 정렬 기준은 이전에 했던 방법인, main에서 선언한 함수를 함수 포인터로 넘겨 대소여부를 비교하는 방식으로 구현함. (main의 비교함수가 true를 반환하면 자리바꿈, 아니면 놔둠) - 이 방식으로 했을 때의 장점: 포인터나 클래스 등 대소판별이 어려운 객체들도 함수에 판별기준을 추가하여 대소판별이 가능해진다. ..
* AVL트리 구현 https://hyrule.tistory.com/59 220419_자료구조_자가균형트리_AVL트리(AVL Tree) 구현 * 필요한 헤더: 링크드 리스트(Linked List) https://hyrule.tistory.com/45 220407~220411_자료구조_링크드 리스트 구현 (Linked List) #pragma once //경고메시지를 띄우기 위한 헤더 #include /* 자료구조 : 데.. hyrule.tistory.com * 실행 코드는 이진트리 실행 코드를 가져옴. https://hyrule.tistory.com/58 220415~220418_자료구조_이진트리(Binary Tree) 실행 * 이진트리 구현 https://hyrule.tistory.com/57 2204..
* 필요한 헤더: 링크드 리스트(Linked List) https://hyrule.tistory.com/45 220407~220411_자료구조_링크드 리스트 구현 (Linked List) #pragma once //경고메시지를 띄우기 위한 헤더 #include /* 자료구조 : 데이터를 관리하는 방법. * 완벽한 자료구조는 없다. 상황마다 적합하고 효율적인 자료구조가 다르다. 그것을 적재적소에 활용하 hyrule.tistory.com //BinaryAVLTree.h /* [자가균형이진트리] * 이진트리의 문제점: 편향트리가 될 가능성이 있다. * 편향트리는 나오는 순간 최악. * 일반 이진트리를 쓸 때 편향트리를 피할 수 있는 방법은 아예 없다.(넣는 데이터에 의존적) * 그렇다고 사용자가 데이터를 직접..
* 이진트리 구현 https://hyrule.tistory.com/57 220415~220418_자료구조_이진트리(Binary Tree) 구현 * 필요 헤더: LinkedList.h https://hyrule.tistory.com/45 220407~220411_자료구조_링크드 리스트 구현 (Linked List) #pragma once //경고메시지를 띄우기 위한 헤더 #include /* 자료구조 : 데이터를 관리하는.. hyrule.tistory.com //main.cpp #include "BinaryTree.h" #include //순회 출력을 위한 함수(이진 트리 클래스에서 주소를 받아서 사용할 예정) void OutputOrder(const int& Key, const int& Value, co..
* 필요 헤더: LinkedList.h https://hyrule.tistory.com/45 220407~220411_자료구조_링크드 리스트 구현 (Linked List) #pragma once //경고메시지를 띄우기 위한 헤더 #include /* 자료구조 : 데이터를 관리하는 방법. * 완벽한 자료구조는 없다. 상황마다 적합하고 효율적인 자료구조가 다르다. 그것을 적재적소에 활용하 hyrule.tistory.com //BinaryTree.h /* [이진트리] * 자식노드가 최대 2개 * 구현방식: 배열기반 or 리스트기반 * 배열기반은 복잡하므로 이진트리로 * 이진트리를 쓰는 이유 : '탐색'이 매우 빠르다 - 추가할때, 삭제할때 규칙이 있음 ex) 루트노드보다 큰건 오른쪽, 작은건 왼쪽에 추가..
*필요 헤더: 링크드 리스트 https://hyrule.tistory.com/45 220407~220411_자료구조_링크드 리스트 구현 (Linked List) #pragma once //경고메시지를 띄우기 위한 헤더 #include /* 자료구조 : 데이터를 관리하는 방법. * 완벽한 자료구조는 없다. 상황마다 적합하고 효율적인 자료구조가 다르다. 그것을 적재적소에 활용하 hyrule.tistory.com //Tree.h /* * 여태까지 우리가 만들어온 자료구조(리스트, 배열 등) = 선형 * 트리는 이와는 다르게 약간 입체적. * 최상단에 루트노드가 존재 -> 나뭇가지처럼 루트노드로부터 뻗어나감 * 규칙성있게 트리 형태를 만들어가는 여러 자료구조가 있다. (이진트리, 쿼드트리, 옥트리 등) * 물론..
//TestClass.h #pragma once #include class CTestClass { public: CTestClass() { testnum = new int; } ~CTestClass() { Test(); } private: void Test() { std::cout
//CircleQueueDynamic.h /* 지난 번에 구현한 서클 큐와 자동 확장 배열 클래스를 응용하여, 용량이 꽉 차면 자동으로 용량을 두 배만큼 늘려 주는 서클 큐를 구현 */ #pragma once #include template class CCircleQueueDynamic { public: CCircleQueueDynamic() { m_Size = 0; m_Capacity = 4; m_Head = 0; m_Tail = 0; m_Array = new T[m_Capacity + 1]; } ~CCircleQueueDynamic() { delete[] m_Array; } private: int m_Size; int m_Capacity; int m_Head; int m_Tail; T* m_Array..
//QueueArray.h #pragma once #include /* * 일반적인 배열로 큐를 만들어버리면 매우 비효율적이다. 큐는 앞에서 데이터를 꺼내고 뒤에 넣는 형식이기 때문에 계속 데이터의 시작점이 뒤로 밀리기 때문이다. --> 그래서 배열로 큐를 만들 때는 '써클 큐' 방식으로 만든다. * 구현 방법: '헤드'와 '테일'을 만들어서 사용한다. 데이터를 꺼낼 때는 헤드에서 꺼낸 뒤 헤드를 뒤로 한 칸 밀고, 데이터를 넣을 때는 테일에 넣은 뒤 테일을 뒤로 한 칸 민다. * 배열의 끝에 갔을 경우, 다시 앞으로 되돌아 올 수 있어야 한다. 예를 들어 크기가 6인 배열일 경우, 6번째 칸(인덱스 5)에 다다르면 다시 0으로 돌아가야 한다 --> 구현 방법 : 나머지 연산자(%) -> 6 나머지는 1..
