정수론 용어 소수(prime number): 약수가 1 or 자기자신인 수 서로소(coprime, relatively prime): 두 정수 a와 b의 공약수가 1인 경우 약수와 배수: b = a*c → a|b or c|b 공배수 a|b이고 c|b → b는 a와 c의 공배수(common multiple) ...

모듈러 연산 a (mod n): a를 n으로 나누었을 때 나머지 11 (mod 7) = 4, -11 (mod 7) = 3 표기 a ≡ b (mod n): b % n = a % n 이라는 의미 n|(a-b)이면 a ≡ b (mod n) a (mod n) ≡ b (mod n)이...

오일러 함수 Φ(n) (Euler Φ function) n 보다 작고 n과 서로소인 양의 정수의 개수. Φ(1) = 1로 정의 오일러 함수에 이용되는 정리들 n과 m이 서로소라면 Φ(nm) = Φ(n)Φ(m) p가 소수이면 Φ(p^k) = p^k–p^(k-1) p^k와 서로소인 수는 p, 2p, 3p, … (p^k...

중국인 나머지 정리 m1, m2, …, mr이 양의 정수이면서 서로소일 때, 임의의 정수 a1, a2, …,ar에 대하여 다음 r 개의 합동식 x ≡ ai (mod mi) (i=1,2,…,r)을 만족하는 정수 x가 존재 예시 x ≡ 1 (mod 3), x ≡ 2 (mod 5), x ≡ 3 (mod 7)을 만족하는 x? ...

다각형 종류 볼록 다각형(Convex Polygon): 모든 내각이 180도 미만인 다각형 오목 다각형(Concave Polygon): 180도가 넘는 내각을 갖는 다각형 단순 다각형(Simple Polygon): 다각형의 경계가 스스로를 교차하지 않는 다각형 볼록 다각형의 특별한 성질 볼록 다각형 내부의 임의의 두 점을 연결하는...

평면 소거법 평면을 수평선 or 수직선(sweep line)으로 아래에서 위 or 왼쪽에서 오른쪽으로 쓸어가며 주어진 문제를 해결하는 기법 2차원의 복잡한 문제를 단순한 1차원 문제로 나누어 해결하는 방식 (sweep line이 1차원 표현) 2가지 자료구조 필요 Event point 순서 결정하는 자료구조 ...

계산 기하학 컴퓨터 알고리즘의 한 분야 기하 물체를 대상으로 하는 문제를 조합론 및 알고리즘적인 해법으로 해결함 컴퓨터 그래픽스, 로보틱스, VLSI 디자인, CAD 등에서 응용됨 기본 기하 연산 벡터의 외적 두 벡터 p = (px, py)와 q = (qx, qy)에 대해서, p X q = pxqy-...

볼록 외피 주어진 점들을 모두 둘러싸는 가장 작은 볼록 다각형 극단점(extreme point): 볼록 외피의 정점이 되는 점 문제 평면 상에 빨간색, 파란색 점들이 주어질 때 직선 L을 그어서 평면을 두 영역으로 나누어 각 영역에 같은 색의 점만 포함하도록 하는 직선 L이 존재하는가? 해결 볼록 외피 이용 빨간 점들...