개념 정렬(Sorting)은 데이터를 특정 기준에 따라 순서대로 나열하는 알고리즘이다. 정렬의 분류 분류 설명 예시 비교 기반 원소 간 비교로 정렬 버블, 선택, 삽입, 퀵, 병합 비비교 기반 비교 ...

개념 연결 리스트는 각 노드가 데이터와 다음 노드를 가리키는 포인터로 구성된 자료구조이다. 메모리상에서 불연속적으로 저장된다 삽입/삭제가 O(1)로 빠르다 (위치를 알고 있을 때) 임의 접근이 불가능하여 탐색은 O(N)이다 포인터 저장을 위한 추가 메모리가 필요하다 종류 종류 설명 ...

데이터베이스란? 데이터베이스(Database)는 조직에 필요한 데이터를 통합하여 저장하고, 여러 사용자가 공유하여 사용할 수 있도록 관리하는 데이터의 집합이다. 핵심 특성 1. 통합 데이터 (Integrated Data) - 중복을 최소화한 데이터의 집합 - 완전한 중복 제거는 불가능하므로 "최소한의 통제된 중복" 허용 2. 저장 데...

개념 알고리즘의 효율성을 분석하는 방법이다. 입력 크기 N에 따라 연산 횟수(시간)와 메모리 사용량(공간)이 어떻게 증가하는지 표현한다. 시간복잡도: 알고리즘이 수행하는 연산 횟수의 증가율 공간복잡도: 알고리즘이 사용하는 메모리의 증가율 실제 실행 시간이 아닌 증가 추세(Growth Rate)에 집중 하드웨어, 언어에 독립적인 분석...

개념 배열은 동일한 타입의 데이터를 연속된 메모리 공간에 저장하는 가장 기본적인 자료구조이다. 인덱스를 통해 임의 접근(Random Access)이 가능하다 메모리상에서 연속적으로 배치되어 캐시 효율이 좋다 정적 배열은 크기가 컴파일 타임에 고정된다 삽입/삭제 시 요소들을 이동시켜야 하므로 비효율적이다 핵심 연산 & 시간...

Security Model for Public Key Encryption Setup - Challenger runs KeyGen($\lambda$) to obtain (pk,sk) and passes a public key pk to Adversary Phase 1 - A asks decryption queries o...

The Diophantine Equation ax+by=c 디오판토스 방정식 : 2개 이상의 미지수를 갖는 방정식의 정수해를 찾는 문제 선형 디오판토스 방정식 : $ax+by=c$ We already proved in Theorem 2.3: If $d=gcd(a,b)$ , then $ax+by=d$ has a solution...

2.4.1 The Euclidean Algorithm $(a \le b < 0)$ Lemma (will be proved) $ a =qb + r \Rightarrow gcd(a,b) = gcd(b,r) $ Proof of $gcd(a,b) = r_{n}$ pf example 숫자가 클수록 모든 positive divisor을 구하...

Definition $ \text{Given } a,b \in \mathbb{Z} \text{ (at least one of them is not zero), } $ $ a,b \text{ are called relatively prime } \overset{\text{def}}{\Longleftrightarrow} gcd(a,b)=1 $ Theo...

Definition Let $a,b\in \mathbb{Z} $. The greatest common divisor of a and b is the positive integer d satisfying $ d \mid a \text{ and } d\mid b$ (common divisor) $ \text{if } c \mid a \t...