[Programmers] '피보나치 수'를 푸는 세 가지 방법

https://programmers.co.kr/learn/courses/30/lessons/12945

 

피보나치 수를 구하는 문제는 보통 재귀로 푸는데 프로그래머에서 그렇게 하면 걍 틀린다! 

시간초과도 나고 런타임 에러도 난다. (그건 바로 나 ^^)

 

피보나치 수를 구하는 문제에는 3가지 방법이 있다! 

 

1. Recursion

첫 번째 방법은 우리가 일반적으로 알고 있는 재귀를 이용한 풀이! 아래처럼 간단하게 풀 수 있다.

 

너무나도 간단하고 직관적이라 좋아보이지만 사실 그렇지는 않다. 

한 함수에서 두 개의 함수를 호출하여 호출이 2배씩 늘어나기 때문에 시간 복잡도가 O(2^N)정도가 나온다. 

좀 더 줄일 수 있는 방법을 찾아보자 !

프로그래머스에서는 테스트 7부터 시간초과, 테스트 13부터 런타임 에러가 떴다. 

 

2. Memorization

메모이제이션도 일반적으로 많이 사용된다. 나는 메모이제이션으로 시간초과를 해결한 적이 많아서 특히 애용하는 방법이다!

 

코드도 위처럼 매우 간단하게 짤 수 있다.

메모이제이션을 이용한 풀이는 시간 복잡도가 O(N)이 나오겠다. 

하지만 테스트 13과 14에서는 런타임 에러가 난다. 

 

 

3. Bottom Up

 

이 방법은 처음 알게 된 방법이다. 

피보나치 수를 N으로 나눈 나머지는 항상 주기를 가지게 된다는 것을 이용한 풀이이다. 

그 주기를 피사노 주기(Pisano Period)라고 한다. 

물론 이 풀이는 배열을 사용하지 않아도 충분히 풀 수 있다. 왜냐하면 저장하는 변수 2개만 있으면 되기 때문! 

 

 

이 세 가지 방법은 https://www.youtube.com/watch?v=vYquumk4nWw&list=PLBZBJbE_rGRU5PrgZ9NBHJwcaZsNpf8yD 를 참고하였다.