c++/자료구조11 20210811 Hashtable 안녕하세요 틴구입니다 오늘은 Hashtable이라는 것에 대해서 적어보려고 합니다. 1.Hashtable Hash Table: 키에 대한 데이터를 저장하는 데이터 구조이고 키만 알면 데이터가 어디에 저장되어있는지 알 수 있는 데이터 구조입니다. 장점 : 데이터 저장/읽기 속도가 빠릅니다. (검색에서 배열보다 해쉬 테이블 구조가 더 빠르다) 검색에서 배열보다 해쉬테이블 구조가 좋은 이유 배열 : index별로 일일이 검색해야, index를 순차적으로 검색할 때 찾고자 하는 데이터가 배열의 마지막 인덱스에 값인 경우 시간이 오래 걸립니다. 해쉬 테이블 : 데이터를 받고 그에 해당하는 키를 찾으면 해쉬 함수를 한 번만 돌리면 바로 그 데이터 저장 위치를 해쉬 테이블에서 찾을 수 있습니다. 키에 대한 해쉬 값이.. c++/자료구조 2021. 8. 12. 20210810 Dijkstra(다익스트라) 알고리즘 안녕하세요 틴구입니다 이번 글은 Dijkstra 알고리즘에 관한 설명입니다 1.Dijkstra 정의 a정점과 b점점 사이의 최단 경로를 찾는 데이크스트라의 알고리즘입니다. 가장 낮은 값을 가진 방문하지 않은 꼭짓점을 선택하고, 방문하지 않은 각 인접 노드와의 거리(가중치)를 계산하고, 작을 경우 인접 거리를 업데이트하는 개념입니다. 단, 음의 가중치가 없는 그래프여야 하고, 방향 그래프, 무방향 그래프 모두 상관없습니다. 2. 이론 설명 위와 같이 1번부터 5번까지의 노드가 있고 그를 연결해주는 엣지와 엣지의 가중치값(Cost)이 있다고 가정을 한다. 이때 처음 시작지점인 1번 노드의 시작 값은 0으로 지정해둔다 여기서 1번에서 4번까지 가는 최단 루트를 구한다고 가정을 했을 때 1번 노드에서 연결되는 .. c++/자료구조 2021. 8. 11. 20210810 Graph알고리즘 안녕하세요 틴구입니다. 안녕하세요 오늘은 자료구조 Graph에 관해서 설명을 해드리려고합니다. 1. Graph란 그래프는 정점과 간선으로 이루어진 자료구조입니다. 그래프를 구현하는 방법에는 인접행렬와 인접리스트방법이 있는데 저 같은 경우는 인접리스트방법으로 구현하도록 하겠습니다. Graph에는 두가지의 종류가있는데 방향성 그래프와 무방향 그래프입니다(배운 가지수가 두가지) 방향성 그래프란 : 방향 그래프는 두 정점을 연결하는 간선에 방향이 존재하는 그래프입니다. 방향 그래프는 그 간선의 방향대로 움직일 수 있습니다. Graph에는 탐색방법이 두가지의 종류가 있습니다 그래프 탐색의 방법은 깊이 우선 탐색(DFS) 방식과 너비 우선 탐색(BFS)방식이 있습니다. 깊이우선 탐색(DFS) : 갈 수 있는 정점까.. c++/자료구조 2021. 8. 11. 20210810 병합정렬(합병정렬) 안녕하세요 틴구입니다. 오늘은 병합정렬에 대해서 설명드리려고 해요~ 병합정렬이란 : 합병 정렬(merge sort)은 하나의 배열을 두 개의 균등한 크기로 분할하고 각 분할된 배열을 정렬한 다음, 두 개의 정렬된 부분 배열을 합하여 전체가 정렬된 배열을 얻고자 하는 것이다. 3, 5, 2, 6, 4, 1, 7, 8 의 배열이 구성되어 있다고 하면 3, 5, 2, 6 | 4, 1, 7, 8 3, 5 | 2, 6 | 4, 1 | 7, 8 3 | 5 | 2 | 6 | 4 | 1 | 7 | 8 이렇게 나뉜다음 돌아가면서 정렬을 이루는 형식입니다 3, 5 | 2, 6 | 1, 4 | 7, 8 2, 3, 5, 6 | 1, 4, 7, 8 1, 2, 3, 4, 5, 6, 7, 8 이런 식으로 요 원리를 알았으니깐 코드.. c++/자료구조 2021. 8. 10. 20210806 Heap정렬, Quick정렬 안녕하세요 틴구입니다. 오늘은 Heap정렬이랑 Quick정렬에 대해서 설명드리겠습니다! Heap정렬 우선 Heap정렬은 이진트리를 베이스로하는 정렬 알고리즘입니다. 그래서 트리에 대한 구조를 이해할 수 있어야하고 이진트리를 이해할 수 있어야 합니다. Heap정렬에는 최대힙과 최소힙으로 나뉘는데 최대힙이란 모든 자료에서 부모노드의 값이 자식노드보다 큰 구조를 의미합니다. 여기서 중요한건 반드시 완전이진트리 구조가 전제가 되어야 합니다. 최대힙은 내림차순 정렬이 됩니다. 최소힙은 부모노드의 값이 자식노드보다 작은 경우를 의미하고 최소힙은 오름차순 정렬이 됩니다. 코드구성 그럼 힙정렬을 구성하는 코드를 만들어 볼게요. 우선 헤더파일에 추가 - 클래스 - 인라인으로 Heap.h를 만들어줍니다. static bo.. c++/자료구조 2021. 8. 8. 20210805 자가균형 이진트리 AVLTree 안녕하세요 틴구입니다. 오늘은 자가 균형 이진트리에 대해서 적어볼까 합니다!! 자가 균형 이진트리란 각 트리의 밸런스를 맞춰주는 알고리즘이란 것을 이용해서 균형을 맞춰주는 이진트리입니다 우선 균형을 맞추는 Revalance 함수를 만들기 전에 균형을 맞출 때 필요한 함수들을 만들어줍니다. 저가 여태까지 해당코드를 비쥬얼 스튜디오에서 코드 타이핑하고 분석하고 주석 달고 복붙을 한 것인데 복습하거나 찾아보려고 할 때 너무 알아보기 힘들기도 하고 해서 이제부터 코드 분석한 내용을 포토샵으로 편집해서 올리겠습니다!! 주석의 경우 선생님이 써 주신 주석 + 저가 나머지 코드 분석한 주석입니다. GetHeight는 인자로 노드값을 넣어 해당 노드의 좌 우측 높이를 알아내는 함수입니다. 삼항연산에 의해서 Height.. c++/자료구조 2021. 8. 6. 20210804 이진 트리 순회, erase 안녕하세요 틴구입니다 오늘은 어제배운 이진트리에서 erase에 관한 녀석들을 적어보도록 할게요 우선 순회라는 녀석에 대해서 설명해드리도록 하겠습니다 이진트리는 3가지의 순회방법이 있습니다 이진트리 순회방법 전위순회, 중위순회, 후위순회 전위순회 : Root -> Left -> Right 의 순서로 구성되어 있고 중위순회 : Left -> Root -> Right 의 순서로 구성되어 있고 후위순회 : Left -> Right -> Root 의 순서로 구서되어 있습니다. (어제의 코드에서 이어짐) public: void PreOrder(void(*pFunc)(const KEY&, const VALUE&)) { PreOrder(pFunc, m_Root); } void InOrder(void(*pFunc)(co.. c++/자료구조 2021. 8. 5. 20210803 이진 트리 (재귀 함수 활용) 안녕하세요 틴구입니다! 오늘은 이진 트리에 대해서 알아보도록 합시다!! 이진트리 정의 이진트리란 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조로, 자식 노드를 각각 왼쪽 자식 노드와 오른쪽 자식 노드라고 합니다. 이진트리는 탐색하는데에 있어서 최적화 되어있다고 합니다. 정확한 이진 트리의 정의는 위키백과 주소 달아놓을게요! https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%ED%8A%B8%EB%A6%AC 이진 트리 - 위키백과, 우리 모두의 백과사전 크기가 9이고, 높이가 3인 이진 트리 컴퓨터 과학에서, 이진 트리(二進-, 영어: binary tree)는 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조로, 자식 노드를 각각 왼쪽 .. c++/자료구조 2021. 8. 4. 20210802 Stack, Queue, CircleQueue 안녕하세요 틴구입니다! 오늘은 링크드에 이어서 Stack, Queue, CirlceQueue에 대해서 알아보도록 할게요. 먼저 Stack부터 알아볼까요? Stack // Stack.h (인라인으로 생성해준다.) #pragma once #include template class CStackNode { // CStack에서 CStackNode의 private을 이용하기 위해 friend를 해준다. template friend class CStack; private: CStackNode() : m_Next(nullptr) { } ~CStackNode() { } private: CStackNode* m_Next; T m_Data; }; template class CStack { public: CStack() {.. c++/자료구조 2021. 8. 3. 20210730 자료구조 erase ~ 정렬, Array class 안녕하세요 틴구입니다 오늘은 자료구조 링크드 리스트에 이어서 erase, 정렬에 대해서 알아보도록 할게요. 어제와 똑같은 파일에서 추가하는 형식으로 해보도록 하겠습니다. 어제와 오늘의 코드 굵기와 구분선을 넣도록 하겠습니다.(맨 아래쪽에 있음) 어제 / 오늘 erase / 정렬 List.h #pragma once #include // friend : 아래처럼 Listnode에 List를 friend로 지정하면 List에서는 ListNode의 // private에 접근할 수 있다. template class CListNode { template friend class CList; template friend class CListIterator; private: CListNode() : m_Next(null.. c++/자료구조 2021. 8. 1. 20210729 자료구조 안녕하세요 틴구입니다 오늘은 자료구조에 대해서 설명해드릴거에요 우선 자료구조는 데이터를 관리하는 방법입니다 자료구조의 종류는 엄청 많은데 그중에서 배열처럼 사용하는 링크드 리스트에대한 코드와 분석을 해보겠습니다 우선 Clist라는 헤더파일을 선언과 구현을 인라인으로 합쳐서 만들어줍니다. 헤더파일 - List.h #pragma once #include // friend : 아래처럼 Listnode에 List를 friend로 지정하면 List에서는 ListNode의 // private에 접근할 수 있다. template class CListNode { // CList에서 CListNode에 접근하기위해 friend를 사용한다 template friend class CList; template friend c.. c++/자료구조 2021. 7. 30. 이전 1 다음
