본문 바로가기
반응형

학업 정리

 (20)
Shell Sort & Selection 주어진 배열을 정렬하는 Shell Sort 함수와 배열에서 n번째로 큰 값을 찾는 Selection 함수를 C언어로 구현했다. 그리고 Main에서는 이 둘을 각각 이용해 배열의 중간값을 찾도록 테스트했다. Shell Sort는 Gap을 어떻게 설정하느냐에 따라 성능이 달라진다. 여기서는 절반씩 줄여나가는 방법과 OEIS A036562 수열을 따르는 방법으로 구현했다. #include #include #include #define N 100000 #define SWAP(a, b, temp) (temp = a, a = b, b = temp) // (For Test) Print all elements in the list. void printList(int list[], int length) { for (in..
거듭제곱수에 대한 나머지 연산 두 양수 A, B에 대해, A^B라는 큰 거듭제곱수를 생각해보자. 예를 들면 66^77 말이다. 이렇게 큰 수에 대해 나머지 연산(modulo, %)을 빠르게 하는 방법은 다음의 특징을 이용한다. (a * b) % n = ((a % n) * (b % n)) % n 예제 66^77의 13에 대한 나머지 연산은 다음과 같다. 66^77 % 13 = ((66^2 % 13)^38 * 66) % 13 = (1^38 * 66) % 13 = 66 % 13 = 1 66^77의 89에 대한 나머지 연산은 다음과 같다. 66^77 % 89 = ((66^2 % 89)^38 * 66) % 89 = (84^38 * 66) % 89 = ((84^2 % 89)^19 * 66) % 89 = (25^19 * 66) % 89 = (((..
El Gamal El Gamal 암호화는 Diffie-Hellman 키 교환 방식을 기반으로 하는 공개키 암호화 방식이다. 수신자는 먼저 다음을 계산한다. 소수 p를 정한다. p보다 작은 x와 g를 정한다. y = (g^x) % p p, g, y를 공개한다. Encryption 전송할 메세지를 M이라 하고 다음을 계산한다. 이때 k는 p보다 작은 임의의 정수로, 공개하지 않는다. a = (g^k) % p b = ((y^k) * M) % p a와 b를 전송한다. Decryption by Third Party 제3자는 x 또는 k를 알아내면 복호화가 가능하다. x나 k를 알아내는 것은 이산 로그 방정식을 푸는 것과 같고, g와 p가 충분히 크면 풀이가 매우 오래 걸려 실효성이 없다(이것은 큰 소수를 알아내는 것이 중요한 이..
RSA RSA(Rivest, Shamir, Adleman)는 공개키 암호화 방식이며, 큰 숫자의 소인수 분해가 NP-문제로 풀기 어렵다는 것을 기반으로 한다(물론, 양자컴퓨터로는 금방 풀릴 것으로 보인다). 먼저, 수신측에서 다음을 계산한다. 서로 다른 두 소수 p, q의 곱인 n을 정한다. Euler's totient (n)을 구한다. 여기서는 (p - 1) * (q - 1)과 같다. 앞서 구한 Euler(n)의 값과 서로소이면서 더 작은 값 e를 정한다. (e * d) % Euler(n) = 1 을 만족하는 d를 구한다. 이후, n과 e를 공개한다. Encryption 메세지 M과 수신측이 제공하는 n, e를 바탕으로 C = (M^e) % n 를 계산한다. 암호문 C를 전송한다. Decryption by T..
Knapsack Cryptography Knapsack Cryptography는 배낭문제(Knapsack Problem)에서 비롯된 공개키 암호화 방법이다. Knapsack Problem에서 Superincreasing Sequence의 경우 다항 시간 내에 해를 구할 수 있지만, General Sequence인 경우 NP-문제가 된다. 수신자(private key를 갖는 쪽)는 다음을 미리 계산하고, H를 공개한다. S = [1, 3, 7, 13, 26, 65, 119, 267] n = 523 (bigger than sum of S) w = 467 (coprime with 523) wi = 28 (467 * 28 % 523 = 1) H = [467, 355, 131, 318, 113, 21, 135, 215] (S * w % n) 여기서 S..
5개의 수에서 중앙값 찾기 (Median Selection) 5개의 수에서 6번의 비교로 중앙값을 찾는 알고리즘을 알아보자. 이 방법은 Selection algorithm의 토대가 된다. 알고리즘 (C++) int median(int list[5]) { int w1, l1, w2, l2; if (list[0] > list[1]) { w1 = list[0]; l1 = list[1]; } else { w1 = list[1]; l1 = list[0]; } if (list[2] > list[3]) { w2 = list[2]; l2 = list[3]; } else { w2 = list[3]; l2 = list[2]; } if (w1 > w2) { if (list[4] > l1) w1 = list[4]; else { w1 = l1; l1 = list[4]; } } else ..
결정 트리 그리기(Decision Tree) 과제로 서로 다른 5개의 수를 가진 배열의 정렬을 위한 Decision Tree를 그려야 했다. 하지만 손으로 그리는게 너무 귀찮은 나머지 코드로 작성해버렸다. 작성언어는 Javascript(ES6)이며, 정렬이 잘 되는지 보기 위한 테스트 코드도 포함되어 있다. 아래 단색의 긴 코드가 너무 보기 힘들 수 있으므로, 사진 파일도 첨부했다. compare = (list, num) => { return (list[parseInt(num / 10) - 1] { if (compare(list, 12)) { if (compare(list, 34)) { if (compare(list, 25)) { // 1/2/5, 3/4 if (compar..
피보나치 수열의 증가 피보나치 수열은 다음과 같다. 번째 피보나치 수를 이라 하자. 이고, 이상의 에 대해 은 다음과 같이 정의된다. 위 식의 양 변을 로 나누면 다음의 식을 얻는다. 이고, 이 5 이상일 때 위 식을 재귀적으로 변형하면 다음의 결론을 얻는다. 그리고 이므로 즉, 이 5 이상일 때 이 성립한다. 그런데 이것은 일 때도 성립함을 확인할 수 있다. 따라서 는 모든 자연수 에 대하여 성립한다. 즉, 피보나치 수열은 이상으로 빨리 증가함을 알 수 있다. 추가 라 하자. (이때 ) 즉, 피보나치 수열에서 인접한 두 항의 비율은 에 수렴하는데, 이 값은 황금비(Golden Ratio)다.

티스토리툴바