피보나치.. 뭘까?... 처음 들어보는 사람도 있을 것이다...
피보나치 피보나치...
피보나치 수에 대한 것을 아래 링크를 참고하면 훨씬 도움이 될 것이다..
https://ko.wikipedia.org/wiki/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98_%EC%88%98
피보나치 수 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 피보나치 수를 이용한 사각형 채우기 수학에서, 피보나치 수(영어: Fibonacci numbers)는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다. 처음 여섯 항은 각각 1, 1, 2, 3, 5, 8이다. 편의상 0번째 항을 0으로 두기도 한다. 피보나치 수가 처음 언급된 문헌은 기원전 5세기 인도의 수학자 핑갈라가 쓴 책이다. 유럽에서 피보나치 수를 처음 연구한 것은 레오나르도 피보나치
ko.wikipedia.org
그럼 피보나치 수를 구현해보도록하자
n이 0이면 0
n이 1이면 1
n이 2이면 ..1이되는데 그전의 값과 그전전의 값을 더한값을 여기서 부터 시작이다..
다이나믹이 보인다 보여 ... 다이나믹 프로그래밍... 사실 이것도 모르는 사람이 있을수도 있으니...
저보다 잘 정리한 사람의 링크를 보시면 됩니다..!!!
https://www.zerocho.com/category/Algorithm/post/584b979a580277001862f182
(Algorithm) 동적 프로그래밍(Dynamic programming) - 배낭 문제, LCS 문제, 막대기 문제
안녕하세요. 이번 시간에는 동적 프로그래밍에 대해 알아보겠습니다. 오랜만에 알고리즘으로 돌아왔습니다. 자료구조는 해시 테이블 빼고는 전부 다루었습니다. 해시 테이블은 이따가 다루겠습니다. 동적 프로그래밍은 이름이 조금 이상한데요. 프로그래밍은 컴퓨터 프로그래밍이라는 뜻
www.zerocho.com
다이나믹을 이용해서 방정식 같은 것을 세우면..
dp[n] = dp[n-1] +dp[n-2] 가 된다.
그럼 이것을 코드로 구현하면??.!!
|
1
2
3
4
5
6
7
8
|
let dp = [];
dp[0] = 0; //첫번쨰 값과
dp[1] = 1; //두번쨰 값은 고정이므로 설정시켜두고...
for(let i=2;i<=n;i++){
dp[i] = Number(dp[i-1])+Number(dp[i-2]);
}
return dp[n];
|
cs |
짜잔~!
추가적인 질문과 피드백은 언제든지 환영입니다!
'알고리즘구현능력 > 문제해결능력' 카테고리의 다른 글
| self assment tree.map 구현에 대하여.... (0) | 2020.01.09 |
|---|---|
| n-queens 체스를 구현해라.. (0) | 2020.01.09 |
| 알고리즘 토이 문제 3번째 부분집합인지 아닌지 불린값 반환문제 (0) | 2020.01.08 |
| 알고리즘 토이 문제 2. 중복되지 않는 문자를 반환하는 문제. (0) | 2020.01.08 |
| 알고리즘 토이 문제 1 풀기. 가위바위보 모든 경우의 수의 배열 구하기.. (1) | 2020.01.07 |
