C++/알고리즘10 [C++] Merging Sort 1. 병합 정렬 : Divide Conquer 기법 이용 1-1. 병합 정렬 알고리즘 동작 과정 재귀문을 돌며 주어진 배열들을 단말노드로 될 때까지 Divide void MergeSort(int * arr, int * tmp, int start, int end) { if (start < end) { int mid = (start + end) / 2; MergeSort(arr, tmp, start, mid); MergeSort(arr, tmp, mid + 1, end); Merge(arr, tmp, start, mid, end); } } 분리된 배열들을 정렬하며 합치는 과정 void Merge(int* arr, int* tmp, int start, int mid, int end) { int idx = st.. 2023. 12. 14. [C++] 이분 그래프(Bigraph) 1. 이분 그래프 (Bipartite Graph) : 인접한 정점끼리 서로 다른 색으로 칠하여 모든 정점을 두 가지 색으로만 칠할 수 있는 그래프 : 이때, 모든 사이클의 길이는 짝수이다 ( ⇔ odd length cycle은 존재하지 않는다 ) 1-1. 그래프 이론 If a graph has no odd cycle then it must be bigraph. 2. 이분 그래프 알고리즘 문제 https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 2-.. 2023. 12. 13. [C++] BST Operations 1. Binary Search Tree : BST에 관한 설명은 아래의 글에서 2023.11.21 - [Python/자료구조] - [python] 이진트리 / 이진 탐색트리(+백준 5639) [python] 이진트리 / 이진 탐색트리(+백준 5639) 1. 이진트리 모든 노드의 차수가 self.data): if(self.right): self.right.insert(item) else: self.right=Node(item) else: raise IndexError def search(self,item,parent=None): if(itemself.data): if(self.right): return self.right.search(item,self) else growingupis.tistory.com .. 2023. 12. 7. [C++] Binary Tree Operations 1. 이진 트리 1-1. 이진 트리 기본 동작 구현 inorder() : LVR preorder() : VLR postorder() : LRV getSize() : 모든 노드의 개수 세는 함수 getHeight() : 트리의 높이 반환하는 함수 containBT() : 트리에 특정 키를 갖는 노드 있는지 true/false로 반환하는 함수 1-1-1. 코드 구현 : 아래와 같은 트리로 구성되게 함 Binary_tree.h #pragma once #include using namespace std; class TreeNode { private: int key; TreeNode* left; TreeNode* right; public: TreeNode(int item) :key(item), left(NULL).. 2023. 12. 5. [C++]Shuffle Doubly linked list 1. 알고리즘 설명 : 연결리스트를 반으로 나누어진 두 개의 연결리스트를 shuffle시키는 알고리즘 ex) 1234567890 → 6172839405 1-1. 알고리즘 동작 Ⅰ. 연결리스트를 반으로(1st half + 2nd half) 나누는 중간 노드를 찾는다 Ⅱ. 기존 연결리스트에서 1st half 연결리스트는 떼고 2nd half 연결리스트만 연결시킨다 Ⅲ. 1st half 연결리스트가 끝에 다다를때까지 기존 연결리스트에 끼워넣는다 1-2. 알고리즘 구현 1-2-1. Doubly linked list with sentinel nodes 2023.11.29 - [C++/자료구조] - [C++]Doubly linked list with sentinel nodes [C++]Doubly linked li.. 2023. 11. 30. [C++]Split Doubly Linked List 1. 알고리즘 설명 : 연결리스트를 반으로 나누는 중간 노드 반환 : 이때 연결리스트를 반으로 나눌 때 노드의 개수가 짝수와 홀수 상관없이 (노드의 개수/2)+1번째 노드 반환 : 노드를 2칸씩 건너뛰어 순회하는 rabbit 노드 + 노드를 1칸씩 건너뛰어 순회하는 turtle 노드로 구성 : rabbit노드가 마지막 노드이거나 tail노드를 가리킬 때의 turtle노드가 중간 노드가 됨 : rabbit 노드와 turtle 노드 모두 첫번째 노드부터 순회 시작 1-1. doubly linked list 2023.11.29 - [C++/자료구조] - [C++]Doubly linked list with sentinel nodes [C++]Doubly linked list with sentinel nodes .. 2023. 11. 29. 이전 1 2 다음
