The Way

c++ algorithm 라이브러리에서는 next_permutation 함수를 기본적으로 제공한다. 그 기능은 일반적인 순열의 순서로 배열 등의 순서를 바꾸어주고,순열이 최종적으로 끝나면(완전히 역순이 되면) 다시 원래 순서대로 바꾼 뒤 false를 반환해주는 함수이다.예를 들어서1 2 3 4 -> 1 2 4 3 -> 1 3 2 4 -> 1 3 4 2 -> ... -> 4 3 2 1 -> (false 반환) 1 2 3 4순으로 작동한다. 또, 중복된 수가 있을 경우 제외해준다.즉, 만약 5가 5개 있다고 치면 5!개의 결과가 나오는 것이 아니라 1개만 나온다는 것이다. 함수를 쓰다보니 함수의 시간 복잡도는 어떤지, 어떤 알고리즘으로 작동하는지가 살짝 미심쩍어서해당 부분 함수 코드를 살펴보았고, 알고리즘이..

$f(x) = a_0 + a_1 x + a_2 x^2 + ... + a_n x^n$이라는 다항식이 있을 때, 이 값은 선형 시간에 계산할 수 있다. 간단한 변환을 거치면 쉽게 알아차릴 수 있는데, $f(x) = a_0 + x(a_1 + x(a_2 + ... + x(a_n + 0)))$으로 변환 가능하기 때문이다. 코드는 다음과 같다. 길이 n+1의 배열은 $a_0,\;a_1,\;a_2,...,a_n$이 저장되어있는 배열이라고 하자 int poly(int x, int* arr, int n) { // n은 배열의 길이 (최고차항+1) int r = 0; for (int i = n; i > 0; --i) { r += arr[i]; r *= x; } r += arr[0]; return r; }

어떠한 알고리즘의 시간 복잡도를 구하기 위해서는 (특히 분할 정복 알고리즘의 경우) 점화식을 풀게 될 때가 많다.가령, 병합 정렬의 알고리즘 복잡도를 구하기 위해서는 다음과 같은 점화식을 풀어야 한다. $$T(n) = \begin{cases}\Theta(1)\;(n=1)\\2T(n/2) + \Theta(n)\;(n>1) \end{cases}$$ 재귀 트리를 작성한다면 직관적으로 복잡도가 $\Theta(n\log n)$임을 알 수 있지만, 마스터 정리를 이용하면 일반적인 경우의 풀이가 쉬워진다. 1. 마스터 정리$T(n) = aT(n/b) + f(n)$형태의 점화식이 있을 때, i) $f(n) = O(n^{\log_b a - \epsilon})$이면 $T(n) = \Theta(n^{\log_b a})$ii..

$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

C++ 코딩용으로 Visual Studio 2015를 사용할 때scanf를 사용하려고 하면 C4996 에러가 발생한다. 해석하자면, scanf 함수가 안전하지 않아 scanf_s를 사용하라고 적혀있다. 또는, _CRT_SECURE_NO_WARNINGS를 사용하라고 한다. 예시 코드는 다음과 같다. #include using namespace std; int main() { int n; scanf("%d", &n); for (int i = 1; i