컴퓨터 프로그래밍(암호학, 알고리즘)

그래프에서는 크게 두 가지 탐색법이 존재한다. 깊이우선과 너비우선 (DFS and WFS) 탐색의 목적은 '어떤 Vertex가 있을까?'하는 'Find'가 아닌, 그래프내에서 모든 Vertex를 Edge를 따라서 '순회'하는데 있다. 즉, 빠짐없이 순회하면서 그 Vertex와 Edge로부터 정보를 얻어서 무언가를 하는데 그 목적이..

기본 구성 점(Vertex)과 간선(Edge)으로 구성 됨 ( Point와 Line이 더 편한 영어표현이나, 알고리즘 책에서 더 많이 쓰는 단어표현이 Vertex, Edge) 그래프의 정의 G(V,E) 표현 방법 3가지 표현 방법: 리스트, 행렬, 위치 1)리스트 vector<list<int>> adj; //혹은 vector<vector<int>> adj; 희소(sparse) ..

소수를 구하는 에라토스테스 체를, 비트단위로 저장하면, 메모리를 절약할 수 있다. (1/8로 줄어듬) 즉, 각 숫자 단위로 한 개의 bool 값을 지정하는 것이 아니고, 비트 1개를 써서 합성수인지 소수인지 가리키게 하는 것. 1바이트면 8비트이기에 8개의 수에 대해 지정 가능.(1~8) 따라서, int로 ..

비트로 표현해서 풀면 편한 문제들이 많다. 이 페이지에서는 비트관련된 유용한 연산들을 소개한다. 비트 연산자들 a & b :and -> a & 7 = a % 8 a | b :or a ^ b :xor -> a ^ 0 = a ~a : not a << b : a를 b만큼 left shift a >> b : a를 b만큼 right shift 비트를 이용한 집합의 표현 꽉 찬 집합을 표현하는 ..

C++관련해서, 알고리즘 문제풀이를 위해 꼭 필요한 부분만을 살펴보자. include 다음과 같은 헤더들을 포함시키는 것을 외워둬야 한다. <stdio.h> //printf, scanf, freopen 함수를 사용하려면, 이 헤더파일을 include해야 함 <iostream> //cin, cout <vector> //vector 클래스 <algorithm> //min, max 함..

이 페이지에서는 Visual Studio 2013을 이용해서 알고리즘 프로그래밍을 하기위해 필요한 설정들에 대해서 다룬다. 다운로드 무료로 사용가능한 Visual Studio Express for Desktop을 다운받아 사용하면 된다. https://www.visualstudio.com/en-us/downloads/download-visual-studio-vs.aspx (설치 시 특이사항 없기에 별도 설..

FHE의 대표적인 라이브러리인 HElib을 이용한 코딩환경을 구축한다. 기본 조건은 다음과 같다. - OS: 우분투 (Windows + cygwin 비추) - 컴파일러: gcc, g++ 사용 - 통합개발툴: Eclipse CDT + makefile 1. 기본 환경 구축(gcc, g++, Eclipse) - home의 사용자 폴더에 'dev'폴더를 만들고, 여기에 필요한 모든 개발툴들..

1. 평균과 기댓값 '평균' '기댓값'은, 아마도 통계에서 가장 먼저 접하고 가장 많이 쓰이는 용어일 것이다. 그럼에도 불구하고, 종종 "평균과 기댓값이 같은 건가?"라는 질문을 받으면, 헷갈린다. 확실히 알아보도록 하자. 예전에는, '기대값'으로 표기했으나, 이제는 '기댓값'이 맞다. 2008년부터, 수학 용어들도 표준 맞춤법의 사이시옷 규칙에 맞게 표기되도록 교과서가 개정되었기 때문. 같은 이유로 '최댓값' '최솟값' '대푯값' '근삿값' '절댓값' '함숫값' 등이 맞는 표기. 평균 (산술)평균은, 어떤 자료가 있을 때, 이 자료를 대표하는 값 중의 하나로, 모든 자료값을 더한 것을 자료의 개수로 나눈 값이다. N개의 자료가 있고, i번째 자료의 값을 xi라고 할 때, 평균 m(mean)은 다음과 같..

문제 이차원 평면상에 위치한 많은 점들이 있다. 두 점 P(x1,y1) Q(x2,y2)의 사이의 거리는 SQRT[(x1-x2)^2 + (y1-y2)^2]로 정의한다면, 모든 점들 사이에서, 가장 가까운 거리를 찾아내시오. 제약조건 각 문제에 대해 답을 찾아내는 시간은 0.5초(500ms 이내)일 것 입력 입력문제는 텍스트파일로 주어지..

문제 an을 구하는 함수인 power(a,n)을, O(log(n))의 실행시간을 갖도록 구현하시오. 풀이 an은 직관적으로 풀면 O(n)이다. private long power_naive(int a, int n){ if(a==0) return 0; long result=1; for(int i=0;i<n;i++){ result = result * a; } return result; } 근데, 이것을 실행시간이 O(log(n))이 되게, Divide and Conquer를 이용해..