[자료구조](23)[집합 & 서로소 집합]

집합집합의 성질중복이 없음순서가 없음집합 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)찾고자 하는 값을 맨 뒤에 넣어 선형탐색의 종료 조건 중맨 끝인가? 를 검사 안해도 됨 특히..

해시 테이블의 구현충돌 처리 없이 간단히 구현하면 다음과 같다.기본 골조문자열 값의 key, int형의 value, 그리고 hash를 저장하는 구조체를 만들고그 구조체를 담는 배열인 bucket을 선언한다.#define CAPACITY 10int current_capacity = CAPACITY;typedef struct { char* key; int value; unsigned long hash;} Entry;Entry* bucket[CAPACITY];해시 함수여기선 간단하게 djb2를 사용하겠다unsigned long hash(const char* str){ unsigned long hash = 5381; //magic number! int c; while (c = *..

이번엔해 (x1, y1)이 가장 작은 정수해라면 모든 해 (xk, yk)를 $x_k+y_k\sqrt{D} \ = (x_1+y_1\sqrt{D})^k$ 로 구할 수 있다.를 증명해보자.2. 모든해를 구할 수 있는지 증명(x1, y1)이 가장 작은 양의 정수해고, (a, b)를 x^2 - Dy^2 = 1의 임의의 양의 정수해라 하자.그리고 (xk, yk)를 $x_k+y_k\sqrt{D} \ = (x_1+y_1\sqrt{D})^k$ 에서 나온 값이라 하자.이때 [[23 정수론 정리]]에서 보인 것처럼 xk, yk는 펠 방정식의 새로운 해다.그리고 z = x1 + y1$\sqrt{D}$ , r = a + b$\sqrt{D}$ 라고 두자.이때 모든 (a, b)가 (xk, yk)로만 나올 수 있으면 정리가 증명된다..

|$x-y\sqrt{D} \ |이를 이용해서 펠 방정식 정리를 증명해보자.펠 방정식 정리D가 제곱수가 아닌 양의 정수일 때 펠 방정식 x^2-Dy^2 = 1에 대해,항상 양의 정수해를 가짐해 (x1, y1)이 가장 작은 정수해라면?모든 해 (xk, yk)를 $x_k+y_k\sqrt{D} \ = (x_1+y_1\sqrt{D})^k$ 로 구할 수 있다. 1. 양의 정수해를 가짐의 증명 디리클레의 디오판토스 근사정리 제 1형식에 따르면|$x-y\sqrt{D} \ |즉, $-\frac{1}{y} 양변에 y$\sqrt{D}$를 더하면 x + y$\sqrt{D}$ 정리하자면, x + y$\sqrt{D}$ 양변에 x-y$\sqrt{D}$를 곱하고, 근사정리 제 1형식을 이용하면,x^2 - Dy^2 즉, 양의 정수해 ..

펠 방정식D가 양의 정수이고 제곱수가 아닐 때,x^2 - Dy^2 = 1 인 디오판토스 방정식해 얻기 펠 방정식의 어떤 해를 x1, y1이라 하자. 1 = (x1^2 - Dy1^2) = ($x_1-y_1\sqrt{D}$)($x_1+y_1\sqrt{D}$) 1^2 = ($x_1-y_1\sqrt{D}$)^2($x_1+y_1\sqrt{D}$)^2 = (x1^2 + y1^2D)^2 - (2x1y1)^2 D 즉, (x1, y1)으로부터 새로운 해 (x1^2 + y1^2*D, (2x1y1)^2)를 얻어낼 수 있다. -> k배를 해서 해를 얻을 수 있다 펠 방정식 정리항상 양의 정수해를 가짐해 (x1, y1)이 가장 작은 정수해라면?모든 해 (xk, yk)를 $x_k+y_k\sqrt{D} ..

삼각수삼각형으로 배열했을 때 총 점의 갯수 . . . 1, 1+2, 1+2+3, ... 으로 표현된다.n번째 삼각수 = n(n+1)/2 사각수사각형으로 배열했을 때 총 점의 갯수. . .. . . 1^2, 2^2, 3^2, ... 으로 표현된다.n번째 사각수 = n^2 사각-삼각수사각수이며 삼각수인 수(단, 몇번쨰인진 따지지 않는다.) 예) 36은 6번째 사각수이자 8번째 삼각수이다.n^2 = m(m+1)/2을 풀어서 구할 수 있다. 양변에 8을 곱해 식을 정리하면 8n^2 = 4m(m+1) = (2m+1)^2 - 1 x = 2m+1, y = 2n으로 치환하면, x^2 - 2y^2 = 1 로 변형 가능하다. 사각-삼각수 정리부정방정식의 해 m, n을 m = (x-1)/2..