서로소인 정수 a와 m에 대해서 a^e ≡ 1 (mod m)을 만족하는 가장 작은 지수 e ≥ 1을 em(a)라고 정의한다a가 m과 n 모두와 서로소이고 gcd(m, n) = 1이라고할 때, emn(a)를 em(a)와 en(a)를 이용하여 나타내어라 위수의 성질에 의해 a^em ≡ 1 (mod m) a^en ≡ 1 (mod n) a^emn ≡ 1 (mod mn) a^■ ≡ 1 (mod m), a^■ ≡ 1 (mod n)꼴로 만들어서 합치고 싶으므로,em, en의 최소공배수 lcm을 잡는다.em * p = en * q = lcm(em, en) a^lcm(em, en) ≡ a^(em * p) ≡ (a^em)^p ≡ 1^p ≡ 1 (mod m) a^lcm(em, en) ≡ a^(en..

펠 방정식은 D가 완전제곱수가 아닌 양의 정수일 때 방정식 x^2−Dy^2 = 1을 말한다.D가 완전제곱수가 아닌 이유를 설명하여라.D = A^2이면 방정식 x^2 − A^2y^2 = 1의 정수해에 대하여 설명할 수 있는가?D = A^2라고 하자. {A > 0}이때 펠 방정식을 인수분해할 수 있다.x^2 − A^2y^2 = (x - Ay)(x + Ay) = 1x, y, A 는 정수이므로, x - Ay, x + Ay도 정수이다.즉, 식을 만족하는 경우의 수는 x - Ay = 1, x + Ay = 1 x - Ay = -1, x + Ay = -1x - Ay = 1, x + Ay = 1두 식을 정리하면x = 1, y = 0 밖에 안나옴x - Ay = -1, x + Ay = -1두 식을 정리하면x = ..

-> 지수에서 합동은 p-1이다.즉, 지표 합동연산은 p-1에서 하고다시 돌아올 때는 p로 복귀!주의mod N -> mod n은 가능하다 (n|N)예) 9 ≡ 5 (mod 4) -> 9 ≡ 5 (mod 2)예) 18 ≡ 2 (mod 16) -> 18 ≡ 2 (mod 4)따라서 mod p에서 합동이면 mod p-1에서도 합동이다.만약 한두번 계산할 거면 그냥 푸는게 낫지만,여러번 특정 mod에 대해 풀거면 지표의 표를 만들고 구하면 빠르게 구할 수 있다.지표의 정의와 연산법칙을 잘 활용하자.$$g^{{I}(a)} \equiv a \ (mod \ p)$$지표의 연산법칙곱셈법칙: I(a) + I(b) ≡ I(ab) (mod p-1)거듭제곱 법칙: I(a^k) ≡ kI(a) (mod p-1) 예) mod 37에..

따로 삽입, 삭제가 필요하진 않으므로,기존의 linked list로 트리를 구현하는게 아니라 배열로 구현한다!-> 빠르고 가벼움 기본 골조인덱스 i의 부모를 저장하는 parent 배열과어떤 집합의 rank를 저장하는 rank 배열을 가지고 구현한다 rank는 root일때만 쓰이므로 그것만 잘 업뎃해주면 됨#define MAX_SIZE 10000int parent[MAX_SIZE];int rank[MAX_SIZE];//자기 자신만 원소로 갖는 트리 생성void init_set(int n){ for (int i = 0; i find최대 O(n)으로 재귀적으로 root를 찾는다.int find(int x){ if (parent[x] != x){ //대표 노드가 나올때까지 탐색 p..

주어진 정수 n이 카마이클 수이고, 소수 p는 n의 약수라 하자. p − 1이 n − 1을 나눈다는 사실을 증명하여라. 또한, p − 1이 사실은 더 작은 수인 n/p − 1을 나눔을 증명하여라. p − 1이 n − 1을 나눈다는 사실을 증명 카마이클 수의 성질에 의해 gcd(a, n) = 1에 대해a^(n-1) ≡ 1 (mod n)=> a^(n-1) ≡ 1 (mod p) mod small은 언제나 성립p는 소수이므로, 원시근 g가 존재하고 a = g라고 두자.g^(n-1) ≡ 1 (mod p)g에서 위수 e = p-1이고,위수의 나눔성질에 의해 e | n-1이다.즉, p-1 | n-1이다. p − 1이 n/p − 1을 나눔을 증명 n = pm이라고 하자.n/p - 1 = m - 1이다.위에서 p-1 ..

집합집합의 성질중복이 없음순서가 없음집합 ADT데이터: 연산삽입삭제탐색 등...해시를 이용한 집합의 구현해시: key 중복 없음, 순서 상관 안함, 매우 빠름-> 해시로 집합을 구현하면 좋겠다 서로소 집합서로 겹치는 원소가 없는 집합-> 효율적인 그룹관리를 위해 만들어짐연산find(x): x가 어떤 그룹 소속인지 반환보통 그룹 내 대표되는 원소를 반환함union(x, y): x, y가 들어있는 그룹을 합침즉 한 집합의 대표 원소를 다른 집합의 대표 원소로 바꾼다연산의 최적화path compression한번 find연산을 한 건 root로 직접 연결한다예) 음식 만약 find(떡)을 한다면 find(국 -> 떡 -> 빵 -> 음식) = 음식이 될 테고, find를 해준 국, 떡, 빵은 이제 자..

배열로 구현하기크기가 100인 배열이라 하겠다. Linear searchint linear(int arr[], int n, int key){ for (int i = 0; i Binary searchint binary(int arr[], int left, int right, int key){ while (left right면 탐색 범위 벗어남 -> 종료 int mid = left + (right - left) / 2; // 오버플로우 방지하며 mid 연산 if (arr[mid] == key){ return mid; } else if (arr[mid] Jump searchint jump(int arr[], int n, int..

피보나치 수열F1 = 1, F2 = 1이고Fn = Fn-1 + Fn-2 인 재귀식을 가지는 선형점화수열성질커지는 비율이 약 1.61803... 정도Fn 이 약 kFn-1 이라고 하자. 이 k를 구해보자.Fn-1 ~ kFn-2, Fn ~ kFn-1 ~ k^2 Fn-2즉, 점화식을 대략적으로 다시 표현하면k^2 Fn-2 = kFn-2 + Fn-2F>0이므로 양변을 Fn-2로 약분한다면,k^2 = a + 1근의 공식을 이용하면$$k = \frac{1+\sqrt{5}}{2}\space or \space \frac{1-\sqrt{5}}{2}$$피보나치 수는 점점 커지는 수열이므로,(1+root(5)) / 2 = 약 1.6180339887498948.... 비네의 공식$a = \frac{1+\sqrt{5}}{2}\..

이항정리이항계수와 이항정리 이항계수n개 중 k개를 뽑는 경우의 수nCk = {n(n-1)(...)(n-k+1)} / {k!}= n! / { (n-k)! k! } 이항계수 덧셈공식nC(k-1) + nCk = (n+1)Ck증명 직접 이항계수 계산해보기 (A+B)^(n+1) = (A+B)^n * (A+B)이용하기 조합론적 접근1~n+1의 수 중 k개를 뽑는다고 하자.그냥 1~n+1 까지 뽑는 경우의 수= n+1이 포함된 경우의 수 + n+1이 포함되지 않은 경우의 수 로나누어질 수 있다.즉, (n+1)Ck = nC(k-1) + nCk 이항정리너무 유명한 거라 적기만 함...$$(A+B)^{n} = \sum_{k=0}^{n}{ {n\choose k}A^{n-k}B^k }$$ ..

내가 찾는게 존재하는가? 그렇다면 어디에?자료구조에 맞는 탐색시간, 메모리, 이식성 따져봐야 함특수 상황에선 특정 알고리즘이 빠를수도? 선형 탐색 (linear search)말 그대로 브루트 포싱인덱스를 1씩 증가시키며 탐색 종료 조건찾았는가?맨 끝인가?사용처소규모의 데이터셋한번만 탐색하고 끝인 경우최선평균최악O(1)O(N/2), 즉, O(N)O(N) 예) 1, 3, 4, 2, 5 에서 2를 찾아라 1->3->4->2 탐색 종료예) 1, 3, 4, 5, 6 에서 2를 찾아라 1->3->4->5->6 끝에 도달한지 검사 -> 종료 보초 선형 탐색 (sentinel linear search)찾고자 하는 값을 맨 뒤에 넣어 선형탐색의 종료 조건 중맨 끝인가? 를 검사 안해도 됨 특히..