순열과 조합

순열

nPr

n개의 원소를 가지는 어떤 집합에서 중복 없이 순서에 상관 있게 r개의 원소를 선택하거나 나열한 것

중복을 허용하지 않기 때문에 반드시 R ≤ N을 만족해야 한다.

조합

nCr
n개의 원소를 가지는 어떤 집합에서 중복 없이 순서에 상관 없게 r개의 원소를 선택한 것

중복을 허용하지 않기 때문에 반드시 R ≤ N을 만족해야 한다.

GCD와 LCM

유클리드 호제법

자연수 a와 b (a > b)의 최대공약수 구하기

a를 b로 나눈 몫 q, 나머지 r이 있다.

이때, 다시 b를 r로 나눈 몫 q와 나머지 r'를 구한다.
다음은 r을 r'로 나눈 몫 q와 나머지 r''을 구한다.
...
이렇게 나머지가 0이 될 때까지 반복하여
마지막 나눗셈에서 나누는 수(r')가 최대공약수가 된다.

= 나머지가 0이 되도록 나누는 수가 최대공약수

멱집합

어떤 집합의 모든 부분 집합을 멱집합이라고 한다.

원소가 있는지, 없는지 2가지를 고려하기 때문에
집합의 요소가 n개일 때 멱집합은 2^n개이다.