CS

피보나치 수열은 0번째 항이 0, 1번째 항이 1, 그리고 그 이후의 항은 앞의 두 항의 합인 수열을 말한다. 점화식으로 살펴보면 다음과 같다. $$ F_0 = 0, F_1 = 1, F_{n+2} = F_{n+1} + F_n (n \geq 0) $$ 피보나치 수열의 n번째 항을 구하는 방법은 여러 가지가 있는데 그 중 3가지를 살펴볼 것이다. 반복 재귀함수 메모이제이션 반복 def fibo(n): if n

순열 (Permutation) 서로 다른 n개 중 순서에 상관있게 r개를 선택하는 경우의 수 서로 다른 n개에서 r개를 택하는 순열의 수는 다음과 같다.예를 들어, 서로 다른 5개에서 3개를 고르는 순열의 수 $_5P_3$은 5 X 4 X 3 = 60 즉, $_nP_r$은 n부터 내림차순으로 r번째 수까지 곱하면 된다. 팩토리얼을 이용하여 간단하게 나타내보면 다음과 같다. $$0!=1,,_nP_0=1,,_nP_n=n!$$ $$ _nP_r=n(n-1)(n-2)\cdot \cdot \cdot(n-r+1),(단,0

에라토스테네스의 체는 소수를 판별하는 알고리즘이다. 2 이상의 수에 대해 소수를 판별할 때 사용할 수 있다. 어떻게 하는지 단계별로 알아보자면 다음과 같다. 2부터 소수를 구하고자 하는 구간의 수를 나열한다. 2는 소수이므로 2는 남기고 2의 배수를 모두 지운다 3도 소수이므로 3은 남기고 3의 배수를 모두 지운다. 이렇게 수를 증가시켜가며 지워지지 않은 수들에 대해 자기자신만 남기고 그의 배수들은 지우는 과정을 반복하면 지정한 구간의 소수들을 구할 수 있다. 지워지지 않은 숫자들이 바로 소수이다. 이때 2부터 N까지 구간의 소수를 구한다고 하면 우리는 $int(\sqrt N) + 1$까지만 확인해보면 된다. 예를 들어 2부터 120까지의 소수를 판별한다고 하면 $120 < 11^2$ 이므로 11까지만 ..

어떠한 양의 정수 N의 약수를 구할 때 간단하게 생각해보면 다음과 같이 1부터 N까지 나누어보면 쉽게 구할 수 있다는 것은 누구나 생각할 수 있다. def get_divisor(num): res = [] for i in range(1, num + 1): if num % i == 0: res.append(i) return res 하지만 이는 O(N)의 시간 복잡도를 가지므로 N이 매우 커진다면 시간 초과로 문제를 풀 수 없을 것이다. 잘 생각해보면 우리는 약수를 구할 때 1부터 N까지 모두 확인해볼 필요가 없다. 우리는 1부터 N의 제곱근까지만 확인해보면 된다. 어떻게 구할거냐면 1부터 N의 제곱근까지의 수들 중 N과 나누어 떨어지는 수들을 구한다. 그 수들을 N에 대해 다시 나누어서 나머지가 0이 되는,..

유클리드 호제법은 두 양의 정수, 또는 두 다항식의 최대공약수를 구하는 알고리즘이다. 호제법(互除法)이라는 말은 서로(互) 나누기(除) 때문에 붙여진 이름이다. 말로 설명하자면 다음과 같다. 두 양의 정수 $a,b (a>b)$에 대하여 $a = bq + r (0 ≤ r a: a, b = b, a if a % b == 0: return b return gcd(b, a % b)$O((log N)^2)$의 시간복잡도로 최대공약수를..