알고리즘 - 피보나치 수열

• 문제

• 내 풀이

피보나치는 기본이지 하고 풀었는데 런타임 에러를 맞았다. 역시 프로그래머스 호락호락하지 않다. 12345678로 나눈 나머지에서 피보나치 수가 커지면서 에러가 나는 것 같은데 어떤 분이 잘 정리해주셨다.

한줄요약: 문제에서 1234567로 나눈 나머지를 정답으로 내놓으라는 것은 문제를 꼰 것이 아니라 int 자료형의 범위 내에 항상 값이 있을 수 있도록 한 배려이며, 자료형의 크기에 제한이 있는 언어를 쓸 경우 (A + B) % C ≡ ( ( A % C ) + ( B % C) ) % C라는 성질을 이용해서 매번 계산 결과에 1234567으로 나눈 나머지를 대신 넣는 것으로 int 범위 내에 항상 값이 존재함을 보장할 수 있다. - 이준희님 -

이 기회에 피보나치를 재귀 말고 다른 식으로도 푸는 법을 알아보자.

새로운 접근

귀염둥이 피보나치를 푸는 법은 두 가지가 있다.

1. 재귀
2. 메모이제이션

1. 재귀

재귀의 문제는 수가 커질수록 불필요한 반복이 많아진다. 예를들어 fib(2)만 해도 벌써 3번 반복된다. --> 시간복잡도가 무려 지수함수!!

2. 메모이제이션

재귀의 중복 호출이라는 문제를 동적 계획법으로 보완할 수 있다! 재귀를 하는 과정에서 한 번이라도 값을 구했다면 저장해 놓으면 되는 것!!!

그러니까 재귀가 돌 때마다 계산한 값을 메모 배열에 n을 index로 저장했다가 그 값이 호출될 때 그냥 메모 배열에서 잡아서 호출하면 된다!

• 대망의 run

피니싱 터치가 필요하다.

• 결과

재귀 한도를 풀라고 하는데 뭔지 모르겠다.. 다른 사람들도 여기서 막힌 거 같은데 파이썬은 재귀 한도를 풀 수 있다는데 자바스크립트는 못 찾아서... 종료! 아무튼 메모이제이션은 일단 성공!

출처 : https://www.youtube.com/watch?v=vYquumk4nWw&list=PLBZBJbE_rGRU5PrgZ9NBHJwcaZsNpf8yD