본문 바로가기

피보나치4

동적 프로그래밍 기초 - 피보나치 수열(메모제이션) 코딩 인터뷰 완전 분석이라는 책에서 동적 프로그래밍 공부의 기초로 피보나치 수열 문제를 다뤘었다. 그 때 메모제이션이라는 기법으로 중복 호출되는 부분을 캐시처럼 저장하여 사용하는 방법이 있어서 한 번 훑고 넘어간 적이 있다. 그런데 딱 그 문제가 릿코드 https://leetcode.com/problems/climbing-stairs/ 에서 나왔다!! 리마인드 할 겸 정리하려한다. 기존의 피보나치의 경우 보통 이런 방식이다. public int climbStairs(int n) { if(n==0){ return 0; } if(n==1){ return 1; } if(n==2){ return 2; } return climbStairs(n-2) + climbStairs(n-1); } 하지만 이 피보나치의 재귀.. 2020. 3. 17.
백준 2747, 2748 피보나치 수 오늘 간단한 피보나치 수열 문제를 풀다가 의외의 복병에 만나서 헤매게 되었다.백준 2747문제 n번 째 = 45 까지백준 2748문제 n번 째 = 90 까지문제의 형태는 같은데 입력 받을 수 있는 수의 크기가 차이나는 문제였다. 2747번 문제를 아무 생각없이 배열과 반복문을 사용해서 제출했는데 "틀렸습니다"왜그런가 하고 재귀함수를 써서 했더니 "정답" 그리고 2748번 문제는 2747을 복붙했더니 역시나 "틀렸습니다"다시 원래 배열과 반복문을 사용했더니 "정답" 왜그럴까? 정답은 속도 차이에 있었다. 2747번 문제는 45번까지라 단순히 재귀함수를 사용해서 풀게끔 의도가 되어있었다. (값이 작음)하지만 2748번 문제는 n 이 90까지인데 재귀함수를 사용할 경우 호출이 누적되면서 실행시간이 매우 오래걸.. 2018. 8. 6.
프로그래머스 피보나치 수 알고리즘 문제는 한번 풀었다고 해서 끝난게 아니고, 실행시간이나 로직들의 최소화에 따라 달라지기 때문에 계속 반복해서 풀어야 할필요성을 느끼게 되었다.그래서 여태 풀어서 블로그에 올렸던 알고리즘들을 완벽히 할 때 까지 반복하려고 한다. - 문제 피보나치 수는 F(0) = 0, F(1) = 1일 때, 2 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 점화식입니다. 2 이상의 n이 입력되었을 때, fibonacci 함수를 제작하여 n번째 피보나치 수를 반환해 주세요. 예를 들어 n = 3이라면 2를 반환해주면 됩니다. 처음에는 재귀함수를 사용해서 문제를 풀었다. 하지만 재귀함수로 할 경우 값이 커짐에 따라 실행시간이 오래 걸려 오답처리가 되었다그래서 반복문을 사용해서 다시 풀었다. 2018. 4. 23.
프로그래머스 멀리뛰기 (level.3) 문제 : 효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는 (1칸, 1칸, 1칸, 1칸) (1칸, 2칸, 1칸) (1칸, 1칸, 2칸) (2칸, 1칸, 1칸) (2칸, 2칸) 의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 출력하는 jumpCase 함수를 완성하세요. 예를 들어 4가 입력된다면, 5를 반환해 주면 됩니다. 이 문제는 단순히 4칸을 가는 방법에 대해서만 구하려고 노력을 했었다. 그러다보니 답을 구하지 못했다. 알고보니 전체에 대한 흐름을 봐야지 풀 수 있는 문제였다. 1칸이 있을 때 = 1(1개) 2칸이 있을 때 = 1+.. 2018. 2. 21.

티스토리툴바