전체 글 썸네일형 리스트형 피보나치 수열의 특징 http://j1w2k3.tistory.com/357 피보나치 수열의 특징, 감사합니다. 더보기 1788번 1788번 - 피보나치 수의 확장 처음에 양수는 양수대로, 음수는 음수대로 구하려고 했다. 양수는 F[N]=F[N-2] + F[N-1] 이라는 식을 쓰고, 음수는 F[N-2] = F[N] - F[N-1] 이라는 식을 써서 풀려고 했다.. 그래서 배열도 늘리고 했는데 점점 복잡해져갔다.. (사실 내가 못했다.. 이렇게 푸신 분도 계심) 그래서 음수를 식에 따라 몇개를 구해보니, 그냥 피보나치 수열과 똑같았다. 다만 -2, -4 ,-6 이때만 음수값이 나오고 F[2]=-F[-2] 와 같았다.. 그래서 그냥 배열도 줄이고 절대값만을 이용해서 답을 구할 수 있었다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445#.. 더보기 2086번 2086번 - 피보나치 수의 합 이 문제는 일단 주어지는 값들의 범위가 너무나 크다. 시간초과가 가장 큰 문제가 됐다. 일단 행렬을 이용하면 N번째 피보나치의 수는 log(N) 의 값에 구할 수 있기 때문에 문제가 되지 않았다. 그래서 처음에는 for문을 통해서 a에서 b까지 피보나치의 수를 모두 구하려고 했다.. 그런데 생각해보니 최악의 경우 a=1 , b=9000000000000000000 이 되면 시간제한 1초를 무조건 넘기게 된다... 구간의 합을 빠르게 구하는 아무리 찾아봐도 O(N)밖에 없었다.. 그래서 다른 분들 코드를 보는데! 피보나치의 수의 합을 빠르게 구하는 식이 있었다. 바로 1에서 N까지의 피보나치 수의 합 = N+2 번째 피보나치 수 - 1 이었다. 이를 이용하면 쉽게 답을 구할 .. 더보기 11444번 11444번 - 피보나치수 6 이번에 기존에 풀던 방식이 메모리 초과가 났다. 그래서 공부를 해보니 피보나치를 행렬로 표현해서 풀 수 있었다.. 그리고 이는 O(logN) 의 시간복잡도를 갖게 되므로 어마어마하게 빠른값을 찾을 수 있었다. (행렬로 계산하게 되면 분할정복의 방식을 사용할 수 있게 되기 때문이다.) 처음에 행렬로 피보나치를 표현해서 뭐하지 했는데, 정말 빨랐다. 그리고 행렬의 곱셈을 미리 풀어봐서 쉽게 풀 수 있었다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818.. 더보기 9471번 9471번 - 피사노 주기 2749번 피보나치 수 3 문제와 아주 똑같이 풀면 된다. 2749번 에서는 나머지를 구했지만, 여기서는 반복되는 구간의 길이만 구하면 된다. 설명은 2749번과 동일 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162#include#includeusing namespace std; //const long long mod = 1000000; int main(){ int P; scanf("%d", &P); while (P--) { vector num; long long N; long long mod; scanf("%lld %l.. 더보기 2749번 2749번 - 피보나치 수 3 이 문제는 피사노의 주기를 공부하면서 풀게되었다. 피사노의 주기는 피보나치의 수를 K로 나누었을 때 , 항상 주기가 생기고 이를 피사노의 주기라고 한다. 2749번은 N의 범위가 어마무시 하다.. 따라서 이를 DP를 이용한 캐시에도 한계가 있어서 , 우선 피보나치의 수를 모두 구할 수 없었다. 그래서 while 문을 통해서 주기를 찾고, 주기를 찾으면 바로 나와서 값을 구하는 방법으로 풀었다. vector 에는 피보나치의 수를 mod 로 나눈 나머지를 계속해서 넣어줬고, 어떤 지점에서 vector 의 첫번째 원소와 같다면, 양 점( i , j ) 를 비교하면서 계속 증가시켜줬다. 그리고 그 때의 i-1 을 저장해둔다. 그래서 j가 i-1까지 가면 주기가 완성되므로 그 값을 .. 더보기 10830번 10830번 - 행렬 제곱 행렬의 제곱을 구하는 방법으로, 행렬의 곱셈과 거듭제곱 수를 구하는 방식의 응용이었다. 나는 multi 함수를 통해 행렬의 곱을, calc 함수를 통해 거듭제곱을 분할정복으로 풀었다. 문제에서 배운점 1. 처음에 이차원 배열을 반환해주는 함수를 만들려고 했으나, 생각보다 어렵고 복잡했다. 그래서 구글링을 해보니, 배열을 반환하는 함수는 vector 나 동적할당을 쓰는 걸로 대체하는게 좋다는 것을 알았다. 그래서 vector 를 이용해서 이차원 배열을 반환해주니까 훨씬 편했다. 2. 처음에 vector 를 초기화 하는 방법은 resize 로 했었다. 그러다보니 이 문제를 풀때 vector v 같은 경우에 v.resize(N) 을 해주고 각 각의 v[i].resize(N) 을 해주.. 더보기 1629번 1629번 - 곱셈 이 문제는 A의 B 제곱을 O(N) 이 아닌 다른 방법으로 풀 수 있는가를 묻는 문제 같다. A의 B 제곱은 for문이 아닌, 분할정복을 이용해서 풀 수 있다. (이진수를 응용해서도 풀 수 있다.) 또한 (A*B)%C = ((A%C)*(B%C))%C 라는 것을 알면 쉽게 문제를 풀 수 있다. 궁금한 점 => 질문게시판 확인 이 문제에서는 int 형 변수를 넘어가기 때문에 전부다 long long 처리 하면 편하다. 내가 궁금한 점은 return 될 때, 결과값이 중요한 것인지, 과정에서 값이 중요한 것인지였다. 1234567891011121314151617181920212223242526272829303132#include using namespace std; int A, B, C;l.. 더보기 이전 1 ··· 41 42 43 44 45 46 47 ··· 61 다음
