나름 개발자의 IT블로그

알고리즘 문제를 풀다 보면 "답이 커질 수 있으니 $1,000,000,007$로 나눈 나머지를 출력하시오" 이런 문장이 많이 보인다. 오늘은 이런 나머지연산에 대한 이야기를 하고자 한다. 피보나치 수 7 15624번: 피보나치 수 7 첫째 줄에 n번째 피보나치 수를 1,000,000,007으로 나눈 나머지를 출력한다. www.acmicpc.net 이 문제를 한번 보자 단순히 문제에서 제시한대로 구현한다면 이런 코드가 나올것이다. n = int(input()) a, b = 0, 1 for i in range(n): a,b = b, a+b print(a%1000000007) 하지만 이렇게 제출하게 되면 시간초과 또는 틀렸습니다를 받는다. 그 이유는 계산 과정에서 a, b의 값이 매우 커지기 때문이다. 이를 ..

피보나치 수는 많은 성질을 가지고 있다. 이 포스트에서 소개하고자 한다. 여기서 살펴볼 피보나치수열은 다음과 같다. $F_1 = 1, F_2 = 1, F_n = F_{n-1} + F_{n-2} \ (n\ge3)$ 1. $\sum_{k=1}^n F_k = F_{n+2} - 1$ 정의에 따라 $F_1 = F_3 - F_2$ $F_2 = F_4 - F_3$ ... $F_n = F_{n+2} - F_{n+1}$ 이다. 그럼 식을 다음과 같이 변형할 수 있다. $F_1+F_2+...+F_n$ $= (F_3-F_2)+(F_4-F_3)+...+(F_{n+2}-F_{n+1})$ $= F_{n+2} - F_2$ $= F_{n+2} - 1$ 이를 통해 $\sum_{k=a}^b F_k $ $= \sum_{k=1}^b F_k..

이전 글에서 피보나치 수를 구하다가 빠른 거듭제곱이 나와 따로 글로 남기게 되었다. 거듭제곱을 위해 다음 코드를 작성하면 $O(N)$의 시간이 필요하다. def pow(a,n): r = 1 for _ in range(n): r *= a return r 위 코드는 거듭제곱을 $a^n=a^{n-1} \times a$ 방식으로 구한다. 이것을 빠르게 해 보자! $n$이 짝수이면 $a^n = a^{n/2} \times a^{n/2}$ $n$이 홀수이면 $a^n = a^{n/2} \times a^{n/2} \times a$ 가 된다. 이제 이것을 재귀적으로 계산하면 된다. 예를 들어 $3^{60}$을 계산해보자 $3^{60} = 3^{30} \times 3^{30}$ $3^{30} = 3^{15} \times 3..

피보나치 수열은 다음 조건을 만족하는 수열이다. $F_0=1, F_1=1, F_n=F_{n-1}+F_{n-2} \ (n \gt 2)$ $1,1,2,3,5,8,13...$ (경우에 따라서 $F_0=0$이 되기도 함) 위 식을 사용해서 구하면 시간 복잡도가 $ O(N) $이기 때문에 $N