# fibonacci

bishoe01

https://school.programmers.co.kr/learn/courses/30/lessons/12945 >문제 설명 피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다. 예를들어 F(2) = F(0) + F(1) = 0 + 1 = 1 F(3) = F(1) + F(2) = 1 + 1 = 2 F(4) = F(2) + F(3) = 1 + 2 = 3 F(5) = F(3) + F(4) = 2 + 3 = 5 와 같이 이어집니다. 2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요 > 1. n번째 피보나치 수 해당 수를 1234567로 나눈 나머지 어? 그냥 피보나치에 %1234567 해주면 되는거 아닌가 ? 해치웠나..? ![](https://velog.velcdn.com/images/b

patangmond329

한동안 알고리즘을 안풀다가 다시 풀어본다. > https://leetcode.com/problems/n-th-tribonacci-number/description/ 1. 문제 2. 내 풀이 3. 다른 풀이 4. memoization 5. 관련된 다른 알고리즘 문제들 6. 피보나치 공식 (binet's formula) 1. 문제 (해석 - 의역) 2. 내 풀이 재귀함수를 이용하여 풀 수도 있다. 3. 다른 사람의 풀이 ahmedengu의 풀이 > https://leetcode.com/problems/n-th-tribonacci-number/solutions/769198/javascript-iterative-recursive-memoization/?orderBy=most_votes&languageTags=javascr

sun202x

사이트: HackerRank 난이도: 미디움 분류: Dynamic programming 문제 기존 피보나치 수열을 변환하여 새로 만든 규칙을 적용하려고 한다. 새로 만든 피보나치 규칙은 다음과 같다. 아래 예시를 한번 살펴보자. 1. 나의 풀이 BigInt를 사용할 수 없는 환경이라서 일단 BigInt를 처리하는 것은 제외하고 작성해 보았다. 피보나치 수열은 전형적인 dp로 해결할 수 있는 문제라서 어렵지 않게 작성했다. 해당 문제를 풀고 다른 사람들의 풀이 방법이 궁금해서 찾아봤는데, 공간 복잡도 조건도 같이 부합해야 한다는 내용을 보게 되어 위 로직을 수정해 보았다. 설명에서는 시간 복잡도와 공간 복잡도를 각각 아래와 같이 표현하였다. > Time complexity: O(n) Space complexity: O(1) 수정된 로직은 아래와 같다. 알고리즘 문제를 작성

ejjang2030

코틀린 인 액션에 다음과 같은 목차가 있다. 리스트 5.12가 다음과 같았다. 혹시 그럼 generateSequence()함수로 피보나치 수열을 만들어 볼 수 있지 않을까 싶어서 한번 구현 시도해보았다. 재미삼아 코딩해보았다.

koo82

피사노 주기: 피보나치 수를 K로 나눴다고 했을 때, 그 나머지는 항상 주기를 가지게 되는데 이를 피사노 주기라 함. 피사노 주기를 P라고 했을 때, N % M == (N % P) % M 또한 $$M = 10^{k}$$ 일 때 k>2라면 주기는 항상 $$15*10^{k-1}$$이라는 공식이 성립함 pisano period 피보나치 수 의 성질 $$F{n+2}\choose F{n+1}$$ = $$1\,1\choose 1\,0$$ $$F{n+1}\choose F{n}$$ $$F{n+1}\,F{n}\choose F{n}\,F{n-1}$$ = $$1\,1\choose 1\,0$$$$^{n}$$ $$F{2n-1}$$ = $$F{n}$$$$^{2}$$ +$$F_{n-1}$$$$^{2}$$ $$F{2n}$$ = ($$F{n-1}$$ + $$F{n+1}$$)$$F{n}$$ = (2$$F{n-1}$$ + $$F{n}$$)$$F_{

hyo123

fibonacci > 문제 -> 피보나치 수열은 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... 위와 같이 정의된 피보나치 수열 중 n번째 항의 수를 리턴하라. > 입력 -> number 타입의 n (n은 0 이상의 정수) > 출력 -> number 타입을 리턴하라. > 주의사항 -> 재귀함수를 이용해 구현해야 한다. 반복문(for, while) 사용은 금지! 함수 fibonacci가 반드시 재귀함수일 필요는 없다. 입출력 예시 의사코드 // fibonacci() 함수를 재귀함수로 만들면 실행시간 초과로 나오므로 내부에 함수를 만들고 그 함수를 재귀함수로 만들자 코드작성

cptkuk91

피보나치 수열 > 0번째 피보나치수는 0이고, 1번째 피보나치 수는 1입니다. > 0, 1, 1, 2, 3, 5, 8, 13, 21, ... 증가한다. 반복문 사용하는 방법이 있지만, 시간 복잡도를 고려했을 때 재귀함수를 사용하는 것이 좋습니다. 피보나치 구하는 재귀함수 그럼 문제를 풀어보자. n번째 요소가 있는 경우 if(newArr[n] !== undefined)가 성립된다. 따라서 newArr[n]들어 있는 숫자를 반환하면 됩니다. 하지만 newArr[n] === undefined 라면 else 문으로 넘어가 getFibo(n - 1) + getFibo(n - 2) 값을 구해서 newArr[n] 넣어줍니다.

yoopark

이 글은 Baekjoon, 피보나치 수를 구하는 여러가지 방법 게시글을 공부하는 용도로 작성하였습니다. 원 게시글이 C/C++로 작성되어 있어서, 필자의 코딩테스트 주력 언어인 Python으로 바꾸어보았습니다. 1단계. 일일이 호출 백준 10870. 피보나치 수 5를 풀 수 있으며, 이 문제에서는 n <= 20 이다. 시간 복잡도 : O(2^N) 거의 두배씩 늘어나니까. 2단계. DP(메모이제이션) 백준 2747. 피보나치 수를 풀 수 있으며, 이 문제에서는 n <= 45 이다. 시간 복잡도 : O(N) 실제 dp 계산은 한번만 하니까. 나머지는 가져다 쓴다. 3단계. DP(타뷸레이션) [백준 2748. 피보나치

kwb020312

문제 설명 효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는 (1칸, 1칸, 1칸, 1칸) (1칸, 2칸, 1칸) (1칸, 1칸, 2칸) (2칸, 1칸, 1칸) (2칸, 2칸) 의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567를 나눈 나머지를 리턴하는 함수, solution을 완성하세요. 예를 들어 4가 입력된다면, 5를 return하면 됩니다. > ### 제한 사항 > ## 입출력 예 > ## 입출력 예 설명 입출력 예 #1 위에서 설명한 내용과 같습니다. _**입출력 예

kwb020312

문제 설명 가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다. 예를들어서 n이 7인 직사각형은 다음과 같이 채울 수 있습니다. 직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요. > ### 제한사항 > ### 입출력 예 > ### 입출력 예 설명

anjinwoong

시작하기 전... $$\phi$$ , $$\psi$$ 를 $$x^2-x-1=0$$ 의 두 근 이라고 하면, > $$\phi=\cfrac{1+\sqrt5}{2}$$, $$\psi=\cfrac{1+\sqrt5}{2}$$ 비네의 공식 (Binet's formula) 음이 아닌 정수 $$n$$ 에 대해 아래의 공식이 성립한다. > $$F_n=\cfrac{\phi^n-\psi^n}{\phi-\psi}=\cfrac{1}{\sqrt5}(\phi^n-\psi^n)$$ 피보나치 수열의 일반항 비네의 공식을 활용하여 피보나치 수의 일반항을 구할 수 있다. > $$a_n=\cfrac{1}{\sqrt5}( \left(\cfrac{1+\sqrt5}{2}\right)^n - \left(\cfrac{1-\sqrt5}{2}\right)^n)$$ $$x \le y$$가 음이 아닌 정수일 때, $$x, y$$ 가 인접한 두 피보나치 수일 필요충분조건은 아래와 같

yhko1992

1. 동적 프로그래밍 동적 프로그래밍(이하 동프) 이라는 말이 직관적이지는 않다. 동프가 도대체 뭘까? 영어 설명을 살펴보자. WTF is Dynamic programming A method for solving complex problem by breaking it down into a collection of simpler subproblems , solving each of those subproblems just once, and storing their solutions. So it is commonly involved in recursion. 복잡한 문제를 간단한 단위로 나누어서 단위별로 문제를 해결하는것을 뜻한다. 주로 나뉜 조각들중에 같은 조각들이 많아서 하위 문제의 답을 저장한다음에 나중에 같은 하위문제가 나왔을때 다시 계산하지 않고 저장한것을 그대로 사용한다. 주로 하위문제가 겹치는 경우와 그 하위문제의 해답이 합쳐져서 최종 답안이 나

jonghwan2_y

- 문제: 아래와 같이 정의된 피보나치 수열 중 n번째 항의 수를 리턴한다. 입출력 예시: 풀이: (주의) 재귀함수를 사용해야 하고, 효율적인 알고리즘(O(N))으로 풀어야 한다. > 아래처럼 단순 재귀함수를 사용하면 효율적이지 못하다. memoization을 활용하자.

boraborayoon

Fibonacci 수열을 구하는 효율적인 알고리즘 O(n)으로 문제풀기 첫번째. 두번째. 두번째 방법은 사실 수학공식을 사용하는 것이라, 코딩구조를 볼 것은 없다..😅

kldaji

문제 https://www.acmicpc.net/problem/1003 > 풀이 메모이제이션을 사용한 다이나믹 프로그래밍! 더 좋은 풀이방법 댓글로 남겨주세요!

moonpiderman

🧑‍💻 피보나치 수 > - 피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다. > - 예시 > > - F(2) = F(0) + F(1) = 0 + 1 = 1 > > - F(3) = F(1) + F(2) = 1 + 1 = 2 > > - F(4) = F(2) + F(3) = 1 + 2 = 3 > > - F(5) = F(3) + F(4) = 2 + 3 = 5 > - 2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요. > 제한 사항 > > - n은 1이상, 100000이하인 자연수입니다. > 입출력 예 > > |n|return| > |:---|:---| > |3|2| > |5|5|

tess

첫 블로그 게시물인데,, 일단 일기 쓰듯 적어본다. 중학교 1학년 과정에서 수학을 포기했다. 피보나치 수열이라는 것은 들어보기만 했지 만들기 위해 노력을 하는 날이 올 줄이야,, 수(num)를 입력 받아 num + 1개 값을 가진 배열을 생성하는 것이 오늘의 목표였다. 제공된 정보는 0번째는 0, 1번째는 1이라는 것. 머릿속으로 굴려보니 알고리즘이 대충 나오게 되었다. 내가 생각한 알고리즘 현재 내가 얻고자 하는 값(n번째)을 구하기 위해서는 방금 구한 값(n-1번째)과 그 전 값(n-2번째)을 더해야 한다. n-1번째 값을 n-2번째 값으로 만들고 n번째 값을 다음 반복에서 n-1번째 값으로 만들어야 한다. 시작조차 어떻게 해야 할지 막막했다. 일단 구한 값들을 모아줄 빈 array를 선언하고, 디폴트 값이자 문제에도 나온 0번째, 1번째 피보나치 수를 이후 나올 반복문에서 쓰일 변수에 할당했다. 이러면 조건문을 쓸 때 좀

limsh_98

설명 : c언어를 활용해 작성한 원형 큐를 가지고 fibonacci생성 원하는 수의 인덱스를 입력하면 해당 인덱스의 숫자가 출력된다.

limsh_98

간단하게 c언어로 작성. 프로그램 설명: 숫자를 입력하고, 1번을 누르면 1에서 해당 숫자까지의 Factorial 값을 알려주고 2번을 누르면 해당 숫자와 가장 가까운 Fibonacci수열의 인덱스값을 알려준다.