The Way

$a^n (mod m)$를 구하는 문제는 RSA 암호 등에서 사용되며 그 중요성이 크다. 단순히 곱해주는 방법이 가장 기본적이겠지만, 분할 정복을 사용하면 더 효율적으로 구하는 것이 가능하다. 보통 오래 걸리는 큰 숫자에서는 mod를 사용하지만, 나머지가 아닌 진짜 수를 원한다면 코드에서 mod 부분을 없애면 된다. 1. 기본적인 방법 숫자를 곱하며 mod 해주는 것을 n회 반복한다. 시간 복잡도는 $O(n)$이다. int pow1(int base, int index, int mod = 10) { long long r = 1; for (int i = 0; i < index; ++i) { r *= base; r %= mod; } return r; } 2. 분할 정복 $a^{2n} = (a^n)^2$이라는 ..

1. 개요Big-O 표기법은 보통 시간 복잡도 혹은 공간 복잡도를 나타내기 위해 주로 사용한다.많은 알고리즘들의 성능을 평가할 때 많이 등장하게 될 것인데, 그 중 한 예시로 정렬에서 다음과 같은 것을 접해보았을 것이다. ex) 정렬 알고리즘의 시간복잡도병합 정렬, 힙 정렬: $O(n\log{n})$삽입 정렬, 선택 정렬: $O(n^2)$ 위 표기의 의미는 간단하게 다음과 같이 이해하기 바란다. /*n개의 원소를 정렬할 때,병합 정렬과 힙 정렬을 하는 데에 걸리는 시간은 $n\log{n}$에 비례하여 증가하고,삽입 정렬과 선택 정렬을 하는 데에 걸리는 시간은 $n^2$에 비례하여 증가한다.*/ 2. 복잡도의 순위 & 낮은 복잡도의 중요성보통 점근 표기법을 할 때는 앞에 붙은 계수는 무시하며, 높은 복잡도..

1. 조합 순열과 조합 시간에 배운 것은 다들 기억하고 있을 것이다. 조합은 보통 다음과 같이 기억하고 있을 것이라고 생각한다. $$_n C_k = \frac{n!}{k!(n-k)!}$$ 이 방법이 조합의 수를 가장 빠르게 구해낼 수 있는 방법이다. 하지만 이번에는 조금 다른 재귀적 성질을 이용해보자. 조합에는 위 식 말고도 다른 재귀적 성질이 하나 존재한다. $_n C_0 = 1$, $_n C_n = 1$$_n C_k = _{n-1}C_{k-1} + _{n-1}C_k$ 척 보면 감이 오겠지만, 위 둘은 base case이고 아래는 재귀적 성질이다. 2. 코드 써있는 그대로 작성하면 된다. int c(int n, int k) { if (k == 0 || n == k) return 1; return c(n..

1. 피보나치 수열이란?피보나치 수열에 대해 길게 설명할 이유는 없으므로 간단히 식만 쓰도록 하자. 누구나 알고 있을 것이라 생각한다.$$F_n = \begin{cases}0 \; (n=0)\\1 \; (n=1)\\F_{n-1}+F_{n-2} \; (n>1) \end{cases}$$ 2. 재귀함수를 사용하지 않고 피보나치 수열 구하기사실 그리 어렵지는 않다.앞의 수를 기억하고 있어야 하므로 0, 1에서 시작해서 (a, b) -> (b, a+b)로 바꾸어주면 된다. int fib1(int n) { if (n == 0) return 0; if (n == 1) return 1; int a, b, t; a = 0; b = 1; for (int i = 1; i < n; ++i) { t = b; b = a + b;..

1. 재귀함수란? 재귀함수란 함수 내에서 같은 함수(자기 자신)가 또 실행되는 함수의 형태를 말한다. 가장 기본적인 형태는 base case와 recursive case 둘을 갖는 형태인데, 가장 유명한 예시인 팩토리얼 구하기를 살펴보자. int fac1(int n) { // base case if (n