우선순위 큐가장 높은 우선순위를 가진 데이터부터 pop하는 자료구조(일반 큐는 삽입 순서로, 우선순위 큐는 우선순위 기준으로 pop)이용CPU의 작업 스케줄러: 중요한 것부터 처리네비게이션 길찾기: 사용자가 어떤 것에 초점을 맞추느냐를 반영응급실: 급한 환자부터 처리우선순위 큐 ADTkey (우선순위): 비교에 이용되는 값데이터연산생성삽입삭제 등...-> 얘도 array, linked list, binary tree 등으로 구현 가능! 힙부모보다 자식이 큰/작은 완전 이진트리(이진 탐색트리 마냥 좌우까지 완벽한 정렬은 아니더라도 부모-자식간은 정렬이 되어 있어야 됨)-> 각 데이터를 인덱스로 접근 가능해 매우 빠름!종류Max heap: 큰 것이 가장 위에 있는 힙Min heap: 작은 것이 가장 위에 있..

AVL 트리앞에서 구현했던 BST의 연산을 이용해 AVL의 self-balancing을 구현하면 된다 heightAVL에서 BF 계산을 위해 height를 계산하는 함수int height(TreeNode* root){ if (root == NULL){ return -1; //자식 노드가 없으면 -1로 처리 // l, r 모두 -1이 나오고 마지막에 +1해서 결국 -1 반환됨 } int l = height(root->left); int r = height(root->right); int max_height = (l>r ? l : r); return max_height + 1;} BFheight 기반 Balance Factor 계산..

BST의 구현기본 골조는 이진트리랑 비슷하지만 BST의 특성을 살려야 함 기본 골조 (일반적인 이진트리)typedef struct Treenode { int data; //int형 데이터 담음 struct Treenode* left; //node를 가리키는 포인터 선언 struct Treenode* right;} TreeNode;TreeNode* makeTreeNode(int data){ Node* newNode = (Node*)malloc(sizeof(TreeNode)); newNode->data = data; newNode->left = NULL; newNode->right = NULL; return newNode;} insertBSTBST의 특성 (작..

연결리스트로 구현이진트리 ADT데이터 연결 리스트로 구현할거라 포인터 필요root: 트리의 맨 위를 가리키는 포인터연산find(): 트리에 있는 데이터 찾기 (이 트리에서는 중복이 없다고 가정한다.)insert_l(): 노드 왼쪽에 데이터 넣기insert_r(): 노드 오른쪽에 데이터 넣기delete(): 트리에 데이터 제거하기기본 골조이거는 포인터가 2개인 것 빼곤 다를 바 없다.typedef struct Treenode { int data; //int형 데이터 담음 struct Treenode* left; //node를 가리키는 포인터 선언 struct Treenode* right;} TreeNode;TreeNode* makeTreeNode(int data){ Node* newN..

순회트리의 모든 노드를 중복 없이 모두 방문하기예시 트리 전위순회루트 -> 왼쪽 노드 -> 오른쪽 노드 순서예) 위 트리를 전위순회로 탐방하면1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7 중위순회왼쪽 노드 -> 루트 -> 오른쪽 노드 순서예) 위 트리를 중위순회로 탐방하면 4 -> 2 -> 5 -> 1 -> 6 -> 3 -> 7스택을 이용한 중위순회 구현스택의 특성을 이용해 중위순회를 구현할 수 있다.리프노드까지 스택에 노드를 넣으면 왼쪽으로 탐색스택에서 노드를 뺄 때 오른쪽 자식 노드 탐색예) 위의 트리에서 스택 S로 중위순회를 한다 하면 S = {1, 2, 4}로 넣어놓고, 4를 pop하고 4는 리프노드이므로 오른쪽 자식 없음, S = {1, 2} 2를 pop하고..

이진 탐색 트리(BST)모든 노드가 다음의 규칙을 만족하는 이진트리 왼쪽 subtree의 모든 값들은 현재 노드보다 작고 오른쪽 subtree의 모든 값들은 현재 노드보다 크다.(단, 보통은 중복 허용 안함) BST의 탐색 찾으려는 값에 따라 작으면 왼쪽, 크면 오른쪽으로 가기 만약 leaf에 도달해도 못 찾았다면 해당 요소가 없다BST의 삽입 적당히 탐색하고 알맞은 위치에 넣기BST의 삭제만약 leaf 노드라면 그냥 삭제만약 leaf 노드가 아니라면해당 노드 기준 왼쪽 subtree의 제일 큰 값또는 노드 기준 오른쪽 subtree의 제일 작은 값을 선택해 노드 삭제한 자리에 넣기연산의 시간 복잡도 최선평균최악탐색O(1)O(logN)O(N)삽입O(1)O(logN)O(N)삭제O..

기존까지 다뤘던 배열, 연결 리스트, 스택, 큐는 선형 자료구조!트리특징부모-자식 관계    root 노드를 제외하면 전부 부모 가짐    leaf 노드를 제외하면 전부 자식 가짐계층의 분화가 일어난다: 여러 레벨로 데이터가 구조화된다.탐색에 효율적임: O(logn)효율적인 삽입 연산현실 반영을 잘 함: 실제 현실의 구조와 많이 비슷함선형 구조보다 더 복잡한 구조 표현 가능배열과 연결 리스트의 단점 보완트리 ADT노드: 데이터가 저장된 요소엣지: 노드 사이를 잇는 선용어뿌리(root), 잎(leaf), 비단말(non-terminal)뿌리: 맨 위에 있는 노드잎: 맨 끝에 있는 자식이 없는 노드비단말: 뿌리도 잎도 아닌 노드부모(parent), 자식(child), 형제(sibling):부모: 어떤 노드를 ..

머지 정렬 (merge sort)배열을 쪼개서 정렬 -> 다시 합치며 정렬예) 4 3 2 1 를 정렬한다면    분할 1: (4 3) (2 1)    분할 2: (4) (3) (2) (1)    병합 1: (3 4) (1 2)    병합 2: (1 2 3 4)void merge(int arr[], int left, int mid, int right) { int i, j, k; int n1 = mid - left + 1; int n2 = right - mid; int* L = (int*)malloc(n1 * sizeof(int)); int* R = (int*)malloc(n2 * sizeof(int)); // 호출될 때마다 요소 개수가 바뀌므로 동적할당 if ..

// 중간에 순서를 바꾸는 경우를 위해 swap 함수를 정의해놨다.void swap(int[] arr, int i, int j){ int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;} 버블 정렬 (bubble sort)옆에 있는 것과 비교하며 계속 이동예) 4 3 2 1 를 정렬한다면    round 1: 3 2 1 4    round 2: 2 1 3 4    round 3: 1 2 3 4-> 정렬 라운드마다 맨 끝의 수가 정렬된다.void bubble_sort(int[] arr){ for (int i = 0; iarr[j+1]) swap(arr, j, j+1) } }}2중 중첩 반복문에 각 반복문마다 ..

큐큐: FIFO방식의 자료구조먼저 들어온 것이 먼저 나간다큐의 쓰임작업 스케줄링네트워킹큐 ADT데이터 큐도 연결 리스트의 일종head: 큐의 맨 앞을 가리키는 포인터rear: 큐의 맨 뒤를 가리키는 포인터연산endqueue(): 큐의 맨 뒤에 데이터 넣기dequeue(): 큐의 맨 앞에 있는 데이터 가져오고 삭제isFull(): 큐가 가득 찼는지 확인 isEmpty(): 큐가 비었는지 확인  배열로 만든 큐기본 골조는 다음과 같다.const int MAX_SIZE = 5;int queue[MAX_SIZE];int head = -1, rear = -1; //큐가 비어있다는 뜻isEmpty, isFullbool isEmpty(int &head, int &rear){ if (head == -1 && re..