heap완전 이진트리니 배열로 구현하기 편하다.(자료구조 12 참고)여기서는 계산상의 편의를 위해 1부터 인덱싱하는 Max힙을 만들겠다. 기본 골조자료를 저장할 배열을 만든다.#define MAX_SIZE 100int heap[MAX_SIZE];int heapSize = 0;그리고 인덱스에 있는 값을 바꿔야 하므로, swap도 정의하겠다.void swap(int* a, int* b){ int tmp = *a; *a = *b; *b = tmp;} 부모-자식 연산인덱스를 가지고 부모 or 자식의 인덱스 계산int parent(int i){ return i/2;}int left(int i){ return 2*i;}int right(int i){ return 2*i+1;} bul..

트리가 complete binary tree이므로N개의 노드가 있을 때 주어진 트리의 최대 높이 H = logN 높이가 h인 부분 트리의 개수 = $\lceil{\frac{n}{2^{h+1}}}\rceil$ 이때 bubbling down이므로 leaf는 계산하지 않는다.(왜냐하면 가장 마지막 부모 노드부터 시작하니까)즉, 높이 h = 0인 노드는 무시하고 시간복잡도를 계산해야 한다.높이가 h인 노드에서 bubbling down으로 내려갈 때 연산은 최대 h번 한다고 할 수 있다.(leaf에선 높이도 0이고 연산도 0번)따라서 bubbling down의 시간복잡도 = O(h) 이제 모든 h에 대해 계산하면$$ 시간복잡도 = O( \sum_{h=0}^{logN}\lceil{\frac{n}{2^{h..

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

페르마 소정리의 제곱근페르마의 소정리gcd(a, p) = 1, p = 소수 => a^(p-1) ≡ 1 (mod p)를 제곱근으로 보기gcd(a, p) = 1일때,A = a^((p-1)/2)라 한다면,A^2 ≡ a^(p-1) ≡ 1 (mod p)이다.즉, p | A^2 - 1 = (A+1)(A-1)이다.by 소수의 가약성, p|(A-1) 또는 p|(A+1)이다.따라서 A ≡ 1 or -1 (mod p)오일러 판정법p가 홀수인 소수, gcd(a, p) = 1이라면a^((p-1)/2) ≡ (a/p) (mod p)이다.증명a = QR즉, a^((p-1)/2) ≡ 1 (mod p)임을 보이자.by 이차잉여의 정의, ∃b, b^2 ≡ a (mod p)이때, b, p가 서로소이므로,by 페르마의 소정리, a^((p-..

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하고..

제곱수의 합동 성질임의의 b에 대해b^2 ≡ (m-b)^2 (mod m)증명(m-b)^2 ≡ m^2 -2mb + b^2 ≡ 0 + 0 + b^2 (mod m)따라서 b^2 ≡ (m-b)^2 (mod m)즉, 제곱수의 합동을 계산하려면 대충 반절까지만 보면 된다.m = 홀수: 1~(p-1)/2 까지 보고 이후는 대칭m = 짝수: 1~p/2 까지 보고 p/2 기준으로 대칭 이차잉여이차잉여(QR): mod p에 대해 어떤 제곱수와 합동인 수 즉, 어떤 b가 존재하여 a ≡ b^2 (mod p)라면 a는 p의 이차잉여이다.이차비잉여(NR): mod p에 대해 어떤 제곱수와 합동이 아닌 수 즉, a ≡ b^2 (mod p)인 b가 존재하지 않는다면 a는 p의 이차비잉여이다.0은 QR도 NR도 아니다.예..

소수의 성질적당한 소수 p, 홀수 q에 대해p - 1 = 2^k*q 꼴이라면 p∤a인 임의의 수 a에 대해 적어도 1개가 참이다.a^q ≡ 1 (mod p)a^q, a^2q, a^3q, ..., a^(2^(k-1)*q) 중 1개는 mod p에서 -1과 합동증명페르마의 소정리에 의해 a^p-1 ≡ 1 (mod p)따라서 a^(2^k*q) ≡ 1 (mod p)case 1: a^q ≡ 1 (mod p) 이라면?a^q(2^k) ≡ 1^(2^k) ≡ 1 (mod p)이므로 만족한다.case 2: a^q !≡ 1 (mod p) 이라면?a^(2^k*q) ≡ 1 (mod p) 이므로a^q, a^2q, a^3q, ..., a^(2^(k-1)*q) 중 제일 마지막 수가 1과 합동이다.따라서 제곱하면 1과 합동이 되는 수 ..