일방향 해시함수 정의 해시함수 중 역상저항성, 제2역상저항성, 충돌저항성을 가지고 있는 함수 해시함수 : 임의 길이의 메세지를 일정 고정 길이의 해쉬 값으로 변환시켜주는 단방향성 함수/알고리즘 역상 저항성(preimage resistance) : 제 1 역상 공격에 대하여 안전한 것 제 1 역상 공격 : 해시값이 주어졌을 때, 그 해시값을 출력하는 입력값을 찾는 공격 단방향 암호화와 관련 있음 단방향 암호화 : A => f => B (암호화) A

주상전치암호 전치 암호란? 치환 암호가 평문 문자를 다른 문자로 어떠한 규칙에 따라 대응시켜 암호화하는 방식이라면, 전치 암호는 평문 문자의 자리를 바꾸는 규칙이다. 즉, 치환 암호는 평문 문자에서 사용하는 문자 집합과 암호문의 문자 집합이 다를 수 있지만, 전치 암호에서는 같다. 또한 문자가 문자로 대응되는 것이 아니라 해당 문자의 위치가 위치로 대응된다. 전치 암호 종류 단순 전치 암호 기존 평문을 주어진 키 값(문장의 길이에 해당하는 순열)로 암호화 한다. 암호화할 때 사용한 암호화 키로 복호화 키를 알아내서 복호화에 사용한다. 따라서 비밀 키 방식을 사용해야한다. 복합 전치 암호 예를 들어 "I AM HEEEUN I AM SENIOR"라는 문장을 전치 암호로 암호화 시킬 때, 주어진 문자 집합에 ..

소수 찾기 프로그램 방법 n-1까지 구하기 O(n) n-1 까지 소수를 모두 구하는 다이나믹 프로그래밍으로 알고리즘 짜기 소수 배열을 만들어서 소수 배열만 돌면서 나누어지는지 판단 O(n) 소수 배열을 만드는 데에 O(n) => 메리트 없음 루트 n까지 돌리면서 짝수 제외하기 O(sqrt(n)) 조건 추가 몇 개의 소수( 3, 5 )를 가지고 해당 수의 배수이면 뛰어넘기 3, 5 계산 시 나누어떨어지지 않았으면 해당 수의 배수에도 나누어떨어지지 않음 구현 시 주의 해당 수가 3으로 나누어떨어지는지, 5로 나누어떨어지는지를 계산하려면 모듈러 연산을 사용해야하는데 시간이 오래 걸림 변수 하나씩 지정하고 1씩 더하는 방법으로 구성 3과 5의 공배수가 나오면 먼저 거치는 3의 if문에서 continue 됨으로 ..

Quick sort '알고리즘' 전공 수업시간에 나온 과제인 '1000만개 데이터 정렬 후 해시 값 구하기'를 하면서 정리한 내용이다. 분할 정복 방법을 통해 구현되는 정렬 방법 시간 복잡도 최악 : O(n^2) 평균 : O(nlogn) 설계를 통해서 개선 가능한 부분 구현 과정 pivot을 선택한다. 위쪽 포인터가 낮은 쪽으로 가면서 피벗보다 작은 수를 찾는다. 아래쪽 포인터가 높은 쪽으로 가면서 피벗보다 큰 수를 찾는다. 두 포인터가 가리키는 요소를 교환한다. 2-4를 반복한다. 두 포인터가 교차한다면 현재 피벗과 해당 위치의 값을 교환한다. 피벗과 피벗보다 작은 section, 피벗보다 큰 section으로 나누고 각 section에 대해 1-5를 실행한다. section의 크기가 0 또는 1이면 ..

QuickSort 논문 brief Part One: Theory 이 sorting은 두 개의 간단한 보조문제로 나뉘어 해결될 수 있는데, 각 문제는 이미 알려진 방식으로 풀 수 있다. Partition : key값을 dividing line에 따라 위 아래로 나누어 이분하는 것 실제로 이 dividing line은 흔치 않고, 있다 할지라도 찾기 힘든데 dividing line이 존재하고 그것의 위치만 안다면 item들을 재정렬하기는 쉬워진다. partition 과정 정렬되어야하는 아이템의 키 중 특정 키를 고른다. 이 키는 bound 라 불린다. dividing line 아래에는 bound보다 작거나 같은 key값이, 위쪽에는 큰 key 값이 오게 한다. dividing line의 위치는 미리 알 필요..

/* 2020-03-19 우희은 삽입정렬 알고리즘 */ #define _CRT_SECURE_NO_WARNINGS #include #include #include #include int buffer[10000000]; // 전역 변수로 넣어야 stack overflow가 나지 않음 void fileOpen() { FILE *fp = fopen("d://algorithm/unsorted10000000.txt", "r"); int i = 0; int tmp = 0; if (fp == NULL) { printf("파일을 열 수 없습니다.\n"); } while (fscanf(fp, "%d ", &tmp)!=EOF) { buffer[i++] = tmp; } fclose(fp); } void insertSortin..

첫번째 과제이다. 시간 복잡도가 f(n)인 알고리즘의 소요시간이 1 nanosecond == 10^(-9) second 이라고 할 때, 왼쪽에 표시된 시간 복잡도를 가지고 있는 알고리즘에 대해 위쪽의 시간 내에 알고리즘이 완료되려면 최대로 어떤 N까지 계산할 수 있을지 알아보자. 대표로 하나를 계산해보면 1sec는 10^(9) nanosec 이므로 n^2의 시간복잡도를 갖는 알고리즘에서 n^2 = 10^(9) 로 두고 풀면 1sec 만에 계산될 수 있는 n 값이 나온다. n 값은 모두 정수로 가정하였다.

세그먼트 트리 https://www.acmicpc.net/blog/view/9 백준님 글 배열 크기 결정 세그먼트 트리를 만들기 위해서 C++의 경우, vector 자료형을 사용하는데 python으로 구현할 것이기 때문에 배열을 사용하려고 한다. 배열의 크기가 얼마나 되어야 할지 가늠하기 위해 크기를 결정해보자. 2의 제곱 수가 리프 노드의 수(n)로 주어진다면 ( 분석해야할 data 갯수가 2의 제곱 수라면 ) 각 단계마다 1/2씩 줄어나가므로 log(n)이 필요한 총 단계(화살표)가 되고 전체 층의 갯수, 즉 높이(h)는 log(n)+1이 된다. 최상위 노드부터 2^(0)개의 노드로 시작하여 층이 증가할 수록 2의 지수 또한 증가하기 때문에 꽉찬 이중 트리(full binary tree)의 총 노드 ..