Algorithm/수학 (5) 썸네일형 리스트형 나머지 연산 (Modulo Operation) Expression n | a: a는 n의 배수이다. a mod n: a를 n으로 나누었을 때 나머지 값 $ a \equiv b\ mod\ n $ : a와 b는 n으로 나누었을 때 그 나머지가 같다. (a와 b는 합동이다, 모듈로 합동) $a \equiv b\ mod\ n $ 이면, a - b는 n의 배수이다. -> $ (a - b)\ mod\ n = 0 $ 나머지 연산 법칙 I. 덧셈 (A+B) % M = ((A % M) + (B % M)) % M II. 뺄셈 (A-B) % M = ((A % M) - (B % M) + M) % M 증명 $ 0 \leq A\%M < M $ $ 0 \leq B\%M < M $ 이므로, $ -M < (A\%M - B\%M) < 2M $ 이다. 따라서 양쪽에 M을 곱해줘야 0.. 이항계수 알고리즘 이항계수 이항계수란 n개의 원소에서 k개의 원소를 뽑아내는 경우의 수를 의미하며, 공식은 다음과 같다. $ \binom{n}{k} = \left\{\begin{matrix} \frac{n!}{k!(n-k)!} & (0\leq k \leq n) \\ 0& (kn) \end{matrix}\right. $ 혹은 $ _nC_k $ 로 나타낸다. 이항계수를 구하기 위한 알고리즘은 여러 종류가 있는데, 이중 몇가지를 정리하겠다. 이항계수의 성질 $ 1. \binom{n}{k} = \binom{n}{n-k} \\ 2. \binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1} \\ 3. \sum_{k=0}^n \binom{n}{k} = 2^n $ 1. 팩토리얼-재귀 방법 $ \binom{.. 소수 판별 소수 찾기 소수 (Prime number): 어떤 자연수 N에 대하여 1과 N으로 밖에 나누어 떨어지지 않는 수 1. 소수의 성질을 이용한 구현 bool isPrime (int N) { for (int i = 2; i*i < N; i++) { if (N % i == 0) return false; } return true; } N이 소수인지 판별하기 위해서는 N-1까지 모두 나눠볼 필요 없이 $ \sqrt(N) $ 까지만 나눠보면 된다. 왜 why? $ N $이 만약 합성수라면 $ p*q $로 표현이 되기 때문에 두 수 중 한개는 항상 $ \sqrt(N) $ 이하, 다른 한 수는 항상 $ \sqrt(N) $ 이상이기에 $ i < N $ 까지 순회하지 않고, $ i \leq \sqrt(N) $까지 순회해도 .. 순열과 조합 순열 $ _nP_r : \frac{n!}{(n-r)!} $ 서로 다른 원소를 가진 집합에서 대상들을 선택하여 순서 있게 배열하는 것 설계 단순히 $ _nP_r $ 을 구하고 싶다면 위의 공식을 이용해서 코드를 짜면 된다. 다만 유의할 점은 팩토리얼은 n이 조금만 커져도 수가 매우 커지기 때문에 위의 식 그대로 보다는 정리된 식을 사용하는 것이 효율적이다. long long permutation (int n, int r) { long long result = 1; for (int i = n; i > n-r; i--) { result *= i; } return result; } 혹은 재귀로 나타낼 수도 있다. long long permutation (int n, int r) { if (r == 0) retu.. 최대공약수, 최소공배수, 소인수분해 1. 소인수분해 소수를 모두 구해서 나눠보는 것 보단 2부터 차례대로 나눠 나머지를 확인하는 것이 더 효율적이다. 왜냐하면 결국 2, 3, 5 등의 소수로 나눠떨어지지 않는다면 그들의 배수인 4, 6, 10.. 등으로도 나눠떨어지지 않을 것이기 때문에 항상 나누는 수가 소수일 때 먼저 나눠떨어지는 효과를 갖기 때문이다. 예를 들어, 24라는 수를 소인수분해하려면 우선 2로 나눠본다. 24 % 2 = 0 나눠떨어지므로 나눗셈의 결과값(몫)인 12를 다시 2로 나눈다. 12 % 2 = 0 나눠떨어지므로 나눗셈의 결과값(몫)인 6을 다시 2로 나눈다. 6 % 2 = 0 나눠떨어지므로 나눗셈의 결과값(몫)인 3을 다시 2로 나눈다. 3 % 2 = 1 나눠떨어지지 않으므로 3으로 다시 나눈다. 3 % 3 = 0 .. 이전 1 다음