피보나치 수열

11778 피보나치 수와 최대공약수 행렬 계산 방법

누가 포스팅 해놓은 것도 없고, 찾으려고하니 왜 이렇게 생각해야 되는게 많은 건지...일단 메모리 제한이 256MB라 메모이제이션 혹은 DP를 생각했는데 .. 시간초가 런타임 에러 뿜뿜...재귀함수를 만들던,, 메모이제이션을 하던 DP를 하던 O(n) 시간이 걸려서 이건 안되겠다...생각했다. 그래서 검색해보니 피보나치 수열을 계산하는 방법 중에 1. 피사노 주기(Pisano Period)2. 행렬 곱셈들이 있었는데 , 1번은 우리가 계산해야 되는 값이 1,000,000,000,000,000,000 처럼 길고 답을 1,000,000 와 같은 값의 나머지로출력할때 유용하게 쓰인다. 10^k로 나눈 피보나치 수의 나머지들을 반복적인 값의 형태를 띈다. 그것을 피사노 주기! 하지만, 피사노 주기도 O(n)이 ..

1003 번 문제 피보나치 함수 Dynamic Programming

DP를 공부하는데 처음 해보면 괜찮을 문제같다. 동전 문제를 바로 해보는 건 조금 어려운것 같기도 하고, 아무튼 0을 호출했을때 0을 출력 1을 호출했을때 1을 출력.이것을 계속 단계 별로 저장해 나아가면서, 최상단의 호출한 번호에서 몇번을 출력해 주었는지 알아내면 된다. DP 배열 0 1 2 3 4 5 6 7 8 9 1/0 0/1 1/1 1/2 2/3 3/5 5/8 . . . dp[0] = 1/0; dp[1] = 0/1;2는 0과 1을 더한 것이고, 3은 2와 1의 결과 값을 더한 것이다. 즉 앞에서 부터, 차례대로 결과값을 쌓아가면 된다. 소스 보기 #include int main(){ int dp[41][2]={0}; int n=0,t=0; scanf("%d",&n); dp[0][0]=1; dp[0..