코코야이야기

공개 키 암호화 시스템(public-key cryptosystem) - 안전하게 키를 분배하는 문제를 해결하기 위해 개발됨 - 메시지를 보낼 때 >> 송신자는 수신자의 공개 키를 찾아 사용하여 암호화한 후 전송 - 메시지를 읽을 때 >> 수신자는 자신이 가진 비밀 키(secret key)를 사용하여 복호화 - 공개 키 암호화 시스템의 구성 조건 >> P 공개 키, S 비밀 키, M 메시지 ① S(P(M)) = M ② 모든 (S, P) 쌍은 유일해야 한다. ③ P로부터 S를 알아내는 것은 M을 해독하는 것만큼 어려워야 한다. ④ S와 P는 쉽게 계산할 수 있어야 한다. 공개 키 암호화 시스템의 기본적인 전제 - 주어진 큰 숫자가 소수인지를 결정하는 빠른 알고리즘은 있지만, 주어진 큰 비소수의 소수 인자를 ..

Birthday Attack (Birthday Paradox) Pq(N, s) = (1-1/N)(1-2/N)¼(1-(s-1)/N) Pd(N, s) = 1-(1-1/N)(1-2/N)¼(1-(s-1)/N) –Pq : s명의 생일이 모두 다를 확률 –Pd : s명 중 2명의 생일이 같을 확률 사람이 임의로 모였을 때 생일이 같은 두 명이 존재할 확률. 생일의 가능한 가짓수는 365개이므로 366명 이상의 사람이 모인다면 생일이 같은 쌍이 반드시 존재. 생일이 365가지이므로 임의의 두 사람의 생일이 같을 확률은 1/365이고, 따라서 365명쯤은 모여야 생일이 같은 경우가 있을 것이라고 생각하기 쉽다. 그러나 실제로는 23명만 모여도 생일이 같은 두 사람이 있을 확률이 50%를 넘고, 57명이 모이면 99%를..

그라함 스캔 http://www.cs.princeton.edu/courses/archive/spr10/cos226/demo/ah/GrahamScan.html 보로노이 다이어그램 http://www.cs.cornell.edu/Info/People/chew/Delaunay.html 최적 이진 탐색 트리 http://www.cs.auckland.ac.nz/software/AlgAnim/opt_bin.html 스트링 편집 거리 http://csilm.usu.edu/lms/nav/activity.jsp?sid=__shared&cid=emready@cs5070_projects&lid=10

AVL 트리 (Adelson-Velskii, Landis Tree) - 러시아의 수학자 Adelson-Velskii와 Landis가 고안한 높이 균형 이진 탐색 트리(height-balanced binary search tree) - 오른쪽 서브트리와 왼쪽 서브트리의 높이 차가 2 이상이 되면 회전을 통해 트리의 높이 차를 1 이하로 유지 - 높이 차 = 오른쪽 서브트리의 높이 – 왼쪽 서브트리의 높이 수행 과정 소스 코드 # include # include # include # include # include using namespace std; const int N = 1000000; //백만으로 double key[N+1]={0,}; double search_key[N+1]={0,}; struct ..

레드-블랙 트리와 AVL 트리 시연 사이트 http://webdiis.unizar.es/asignaturas/EDA/AVLTree/avltree.html

레드-블랙 트리 (Red-Black Tree) - 2-3-4 트리를 표준 이진 트리로 표현하는 방법 - 노드당 추가로 1 비트가 더 필요함 - 블랙 링크는 보통의 노드이고, 3-노드와 4-노드는 레드 링크로 연결된 이진 트리로 표현 성질 - 루트나 외부 노드는 모두 블랙 - 루트에서 외부 노드까지의 경로 상에는 2개의 연속된 레드 노드가 포함되지 않음 - 루트에서 각 외부 노드까지의 경로에 있는 블랙 노드의 수는 모두 같음 - 동일한 키를 가지는 레코드는 노드의 왼쪽과 오른쪽에 모두 올 수 있음 - 동일한 키가 여러 개 있을 때 주어진 키를 갖는 모든 노드를 찾는 것이 어려움 4-노드의 분할 4-노드의 분할 (회전 필요) 단일 회전 이중 회전 구축 과정 키(2, 1, 8, 9, 7, 3, 6, 4, 5)..

2-3-4 트리 (2-3-4 Tree) 이진 탐색 트리(1개의 키, 2개의 링크)에서 발생하는 최악의 상황을 방지하기 위해 다음과 같이 자료구조를 변경 - 트리에 있는 하나의 노드가 하나 이상의 키를 가질 수 있음 - 3-노드(2개의 키, 3개의 링크)와 4-노드(3개의 키, 4개의 링크)를 허용 - 트리의 균형에 대해 신경 쓰지 않아도 완벽한 균형 트리가 만들어 짐 분할 과정 1. 루트가 4-노드인 경우 - 세 개의 2-노드로 변환 - 루트의 분할은 트리의 높이를 하나 증가시킴 2. 부모가 2-노드인 4-노드의 경우 - 중간 키를 부모로 보내여 3-노드에 연결된 두 개의 2-노드로 변환 3. 부모가 3-노드인 4-노드의 경우 - 4-노드에 연결된 두 개의 2-노드로 변환 4. 4-노드가 2-3-4 트리..

이진 탐색 트리 (Binary Search Tree) - 작은 키를 가지고 있는 모든 레코드는 왼쪽 부분트리에 있음 - 같거나 큰 키를 가지고 있는 모든 레코드는 오른쪽 부분트리에 있음 탐색 과정 - 루트와 주어진 키를 비교 - 키가 루트보다 작다면, 왼쪽 부분트리로 이동 - 키가 루트와 같다면, 종료 - 키가 루트보다 크다면, 오른쪽 부분트리로 이동 * 트리를 중위 순회하면 데이터를 정렬하는 효과가 있음 예시 성능 특성 - N개의 임의의 키로 이루어진 이진 탐색 트리를 탐색하고 삽입하는 연산은 평균적으로 logN 회의 비교 필요 - 최악의 경우 N 개의 키를 가진 이진 탐색 트리를 탐색하는데 N 회의 비교 필요 >> 키가 정렬되거나 역순으로 정렬된 순서로 삽입 >> 최초 비어 있는 트리에 키들이 A Z..

히프 정렬 (Heap Sort) 히프(heap)를 이용해 정렬 (히프 : 우선순위 큐의 일종) - 정렬할 원소를 모두 공백 히프에 하나씩 삽입 - 한 원소씩 삭제 →제일 큰 원소가 삭제됨 - 이 원소를 리스트의 뒤에서부터 차례로 삽입 - 오름차순으로 정렬된 리스트를 생성 히프 구성 방법 - 상향식(bottom-up) : 정렬할 배열을 완전 이진 트리라고 간주하고, 인덱스가 N/2인 노드부터 차례대로 인덱스를 감소시키면서 히프 구조로 변환 - 하향식(top-down) : 공백 히프에 차례대로 한 원소씩 삽입하여 히프를 구성 상향식 히프 구성 수행 과정 성능 특성 - 제자리 정렬이지만 불안정적 - N 개의 원소를 정렬하는데 N logN 단계가 필요함 - 입력 배열의 순서에 민감하지 않음 - 내부 루프가 퀵 ..

자연 합병 정렬 (Natural Merge Sort) - 주어진 배열 속에 이미 순서에 맞는 원소로 된 부분 배열, 즉 런(Run)만을 합병. - 두 개의 런이 결정되면 합병이 수행된다. 예를 들어 배열 [6, 7, 8, 3, 4, 1, 11, 12, 13, 2]에서 런 [6, 7, 8]과 런 [3, 4]가 먼저 합병되면 [3, 4, 6, 7, 8]이 되고 런 [1, 11, 12, 13]과 런 [2]가 합병되면 [1, 2, 11, 12, 13]이 된다. 마지막으로 런 [3, 4, 6, 7, 8]과 [1, 2, 11, 12, 13]이 합병되면 [1, 2, 3, 4, 6, 7, 8, 11, 12, 13]이 된다. 소스 코드 1. #include #include using namespace std; const..