알고리즘 문제를 위한 수학공식

1. 오랜만에 다시 보는 것들..

• 순열 : nPr = n! /(n-r)!
• 조합 : nCr= n! / r! (n-r)!
• 약수 : 어떤 수를 나누어떨어지게 하는 수
• 배수 : 어떤 수의 1,2,3,…n 배하여 얻는 수
• 공약수 : 둘 이상의 수의 공통인 약수
• 공배수 : 둘 이상의 수의 공통인 배수
• 최대 공약수(GCD. Greatest Common Divisor): 둘 이상의 공약수 중에서 최대인 수
• 최소 공배수(LCM. Least Common Multiple): 둘 이상의 공배수 중에서 최소인 수
• 멱집합 : 어떤 집합이 있을 때, 이 집합의 모든 부분집합 -> 멱집합을 구하는 방법에서 각 단계를 유심히 살펴보면, 순환 구조를 띠는 것을 확인할 수 있다. 여기서 순환구조는 임의의 원소를 제외하면서 집합을 작은 단위로 줄여나가는 방법이다. 따라서 문제를 작은 단위로 줄여나가는 재귀를 응용할 수 있다.