인수분해와 산술의 기본정리소수 p가 p|ab이면, p|a 또는 p|b여야 한다증명만약 p|a 이면 참이므로 증명 끝만약 p|a가 아니면    gcd(p, a)|p이므로, gcd(a, p) = 1 or p    gcd(p, a)|a이므로 gcd(a, p) = 1    선형방정식의 정리에 의해 ax+py=1을 만족하는 x, y존재.    양변에 b를 곱하면, bax+bpy=b    p|pb, p|ab이므로 방정식의 우변인 b에 대해서도 p|b다.소수의 가약성: p|a1*a2*...*an 이면 p는 a중 적어도 1개를 나눈다증명p|a1이라면 참이므로 증명 끝만약 p|a1가 아니면    앞에서 증명한 정리에 따라, p|a1(a2a3...ar)에서 p|a2a3...ar을 만족해야 한다.이걸 r번 반복해 p가 a중..

ax+by 꼴로 표현되는 가장 작은 양의 정수는 gcd(a, b)다.증명gcd(a, b) | ax+by이므로 참유클리드 호제법으로 ax+by=gcd(a, b) 해 구하기방법&증명a = b*q1+r1b = r1*q2+r2r1= r2*q3+r3...r(n-3) = r(n-2)*q(n-1)+r(n-1)r(n-2) = r(n-1)*q(n)+r(n)r(n-1) = r(n)*q(n+1)+0라고 유클리드 호제법을 한 뒤,r1 = a - b*q1 처럼 정리하고 다음 식에 대입하면,결국 r(n) = a(...) + b(...) 꼴로 정리되므로이 방법으로 구하면 된다.예) 22x+60y=2 (단, gcd(22, 60) = 2)22 = a, 60 = b라 두고,60 = 22*2 + 16 -> 16 = b - 2a22 = 1..

머지 정렬 (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 ..

모든 소수 p에 대해 (p-1)! = p-1 (mod p)인가?p = 2에서 증명1 = 1 (mod 2) 이므로 참p = 3에서 증명2 = 2 (mod 3) 이므로 참p > 3에서 증명선형합동방정식의 정리에 의해 ax ≡ b (mod m), gcd(a, m) = 1일때유일한 해를 가진다. (x=bu/g, au+mv=1)(p-1)! (mod p)에서도 p-1, p-2, ... 1은 모두 p와 서로소 관계이다.따라서 aa' ≡ 1 (mod p)인 a'도 0~p-1 범위 내에 유일하게 가진다.이때 특수한 경우인 x^2 ≡ 1 (mod p)를 만족하는 x = 1, p-1 말고 나머지는 2~p-2가 짝수개이므로서로 짝지을 수 있다.a ≡ b (mod m1), a ≡ b (mod m2)⇒ a1a2 ≡ b1b2 (m..

// 중간에 순서를 바꾸는 경우를 위해 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..

스택스택: LIFO방식의 자료구조먼저 들어온 것이 나중에 나간다스택의 쓰임ctrl+z수식의 valid 평가 (괄호 판별)함수 호출 관리스택 ADT데이터 스택도 연결 리스트의 일종top: 스택의 맨 끝을 가리키는 포인터연산push(): 스택의 맨 위에 데이터 넣기pop(): 스택의 맨 위에 있는 데이터 가져오고 스택에서 삭제peek(): 스택의 맨 위에 있는 데이터 가져오기만 하기isFull(): 스택이 가득 찼는지 확인 isEmpty(): 스택이 비었는지 확인  배열로 만든 스택기본 골조는 다음과 같다.const int MAX_SIZE = 5;int stack[MAX_SIZE];int top = -1; //스택이 비어있다는 뜻isEmpty, isFullbool isEmpty(int &top){ if..

연결 리스트: 데이터와 그 다음을 가리키는 포인터를 저장하는 자료 구조리스트의 유동성은 여기서 나온다!종류singly linked list: 한 방향으로만 포인터가 있는 연결 리스트doubly linked list: 앞, 뒤로 포인터가 있는 연결 리스트circular linked list: 끝의 포인터가 맨 앞을 가리키는 연결 리스트연결 리스트 ADT데이터: node 라고 불림head: 리스트의 시작을 저장하는 포인터tail: 리스트의 끝은 저장하는 포인터 (굳이 없어도 됨)연산삽입삭제방문 등...실제 구현 (singly linked list)기본 뼈대데이터와 포인터로 이루어진 구조체 정의typedef struct node { int data; //int형 데이터 담음 struct node* ..

용어    a|b: a가 b를 나눈다 = a는 b의 약수다    공약수: 두 수를 모두 나누는 수        즉, d|a, d|b인 d는 a와 b의 공약수    최대공약수: 공약수 중 가장 큰 수예전에 공약수를 구할 때는 오로지 자연수 범위에서 했지만, 이제는 정수 범위에서 구할 수 있다.예) 12, 18의 공약수는?    (자연수 범위): 2, 3, 6    (정수 범위): -2, -3, -6, 2, 3, 6  gcd(a, b): a와 b의 최대공약수    예) gcd(12, 18) = 6    gcd(0, k) = k    gcd(0, 0) = ? (정의 안함)    gcd(m, n) = 1   유클리드 호제법: gcd 빠르게 구하기예) gcd(36, 132)    132 = 36 * 3 + 24 ..

피타고라스 세 수와 단위원의 관계a^2+b^2 = c^2에서 c^2로 나눠보자.(a/c)^2+(b/c)^2=1 즉, x^2+y^2=1인 단위원 위의 점 (a/c, b/c)이다. 단위원 위의 유리수 점단위원 위의 모든 유리수 점의 좌표를 구해보자.단위원 위의 모든 유리수 점의 좌표는 (-1, 0)을 지나고 기울기가 유리수 m인 y=m(x+1)과 단위원의 교점으로 생각할 수 있다.x^2+y^2=1에 대입하면,x^2+(m(x+1))^2=1=> (x+1)((m^2+1)xm^2-1) = 0즉, 유리수 점의 좌표는 ((1-m^2)/(1+m^2), (2m)/(1+m^2))에 m을 대입해 얻을 수 있다.(단, m->무한 인 (-1, 0)만 빼고...) 피타고라스 세 수와 단위원 위의 점m=유리수=v/u (v, u=정수..