파이썬에서 어떤 정수의 거듭제곱을 구한다면 **을 사용한다 print(3**2) 9 그런데 사실 -1의 거듭제곱은 홀수번 거듭제곱하면 -1이고 짝수번 거듭제곱하면 1이다. 그래서 단순히 n이 짝수인지 홀수인지에 따라 (-1)**(n)을 바로 계산할 수 있다 그래봤자 큰 차이 없는거 그냥 하면 되는거 아니냐? 라고 생각할 수 있는데, 한두번 계산하는건 크게 차이 없지만 n이 충분히 클때 (-1)**(n)을 여러번 계산하면 시간차이가 3~4배 정도로 차이가 난다
1. 문제 15996번: 팩토리얼 나누기 (acmicpc.net) 15996번: 팩토리얼 나누기 음이 아닌 정수 N와 소수(prime number) A가 주어지면, N!을 Ak로 나누었을 때, 나머지가 0이 되는 최대의 음이 아닌 정수 k를 구하여라. (단, N!=N×(N-1)×···×1, 0!=1) www.acmicpc.net 2. 풀이 n의 범위가 $2^{31} = 2147483648$까지로 이것의 팩토리얼을 계산하면... 상상하기도 힘든 숫자가 나올거는 뻔하니 계산하지 않고 $A^{k}$로 나눠보라는 말일텐데 어떻게 가능할까 예를 들어 생각하면 생각보다 간단한 문제다 5! = 5*4*3*2*1인데 $2^{k}$로 나눈 나머지가 0이 되는 최대의 k는 어떻게 찾을까 만약 k = 0이면 당연히 5!은 ..
1. 에라토스테네스의 체 기본형태 n이하의 소수를 구하는 알고리즘 n+1개의 1을 가지는 리스트로 초기화하고, 2부터 n의 제곱근까지 순회하여 해당 수의 배수를 모두 지우고 나면 소수만 남는다는 알고리즘이다 n = int(input()) result = [1]*(n+1) for i in range(2,int((n+1)**(1/2))+1): if result[i] == 1: for j in range(i*i,n+1,i): result[j] = 0 prime_list = [i for i in range(2,n+1) if result[i] == 1] 여기서 j의 시작 지점을 i+i로 하는 경우가 많은데, i*i로 해도 된다. 왜냐하면, i+i는 결국 가장 먼저 2의 배수에서 지워지기 때문이다. 2. 에라토스테..
1. 피보나치 수열의 행렬 표현 피보나치 수열의 점화식은 다음과 같다. $a_{n+1} = a_{n} + a_{n-1}$ $a_{n} = a_{n} + 0$ 따라서 행렬로 나타내면 다음과 같다 $$\begin{pmatrix} a_{n+1} \\ a_{n} \end{pmatrix}=\begin{pmatrix} 1 & 1 \\ 1 & 0 \\ \end{pmatrix}\begin{pmatrix} a_{n} \\ a_{n-1} \end{pmatrix}$$ n = 1부터 반복적으로 곱해보면... $$\begin{pmatrix} a_{2} \\ a_{1} \end{pmatrix}=\begin{pmatrix} 1 & 1 \\ 1 & 0 \\ \end{pmatrix}\begin{pmatrix} a_{1} \\ a_{0..
1. 문제 E - Geometric Progression (atcoder.jp) E - Geometric Progression AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 정수 A,X,M이 주어질 때, $$\sum_{k=0}^{X-1} A^{k}$$를 구하는 아주 간단한 문제 2. 풀이1 이미 재귀로 푸는 방법을 배운적 있다 컴퓨터가 등비수열의 합을 구하는 방법 (tistory.com) 컴퓨터가 등비수열의 합을 구하는 방법 1. 문제 15712번: 등비수열 (acmicpc.net) 15712번: 등비수열 첫째 줄에 a..
1. 문제 15712번: 등비수열 (acmicpc.net) 15712번: 등비수열 첫째 줄에 a, r, n, mod가 공백으로 구분되어 주어진다. a, r, n, mod는 모두 1보다 크거나 같고, 109보다 작거나 같은 자연수이다. www.acmicpc.net 초항이 a, 공비가 r, 항 수가 n인 등비수열의 합을 mod로 나눈 나머지를 구하는 간단한 문제 초항이 a이고 공비가 r이며 항 수가 n인 등비수열의 합은.. 공비 r이 1이 아니면, $$S = a \times \frac{r^{n}-1}{r-1}$$ 이라는 아주 쉬운 공식이 있고 이거에 따라 계산해서 mod로 나눈 나머지 구하면 되는거 아니냐 라고 쉽게 생각하면 이 문제는 풀수가 없다 a,r,n이 작으면 상관 없겠지만... 매우 크면 $r^{n..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
