이항계수 이항 계수는 주어진 크기의 주어진 크기 집합에서 원하는 개수만큼 순서없이 뽑는 조합의 가짓수이다. 전체 집합에서 원소의 개수 n에 대해 k개의 아이템을 뽑는 이항계수(조합의 수)는 다음과 같이 정의한다. 이항 계수의 값을 삼각형 모양으로 나열한 표를 파스칼의 삼각형이라고 한다. 이항계수의 성질 이항 계수는 다음과 같은 항등식을 만족한다. 그리고 다음과 같은 점화식이...

소수 소수는 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다 모든 자연수는 소수의 곱으로 나타낼 수 있다는 규칙이 있다. 84 = 2^2 * 3^1 * 5^0 * 7^1 * 11^0 * 13^0 * 17^0 * … 위 수식에서 많은 소수의 지수 부분이 0이다. 가분성(divisibility) 어떤 수...

Fibonacci Number 피보나치 수는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다. 재귀함수 사용 Recursion 관점에서의 접근 f0 = 0 : Base case f1 = 1 : Base case fn = fn-1 + fn-2 if n>1 : Recursion case function fibonacci(n) { if...

최대공약수와 최소공배수 x와 y의 최대공약수(greatest common divisor) 적어도 하나가 0이 아닌 정수들의 최대공약수는 공약수 가운데 가장 큰 하나다. 지수를 이용한 방법 두 수의 공통인 지수 중에서 작은쪽의 곱이 최대공약수이다. gcd(x, y) = 2^min(j0, k0) * 3^min(j1, k1) * 5^min(j2, k2) * … 유클리드 호제법 m>n인 두 양의 정수 m과 n에...

Recursion 재귀함수 자기 자신을 호출하는 함수 무한 루프에 빠지지 않도록 조건을 잘 세워야한다. Base case: 적어도 하나의 recursion에 빠지지 않는 경우가 존재해야 한다. Recursive case: recursion을 반복하다보면 결국 base case로 수렴해야 한다. 기본적인 수학함수에서의 Recursion 예 Factorial: n! Recursion 관점에서의 접근 0! = 1 : Base case n! = n...