피보나치 수

프로그래머스 레벨2 [정답율 72%]
❓문제

❗문제 정리
사용한 파라미터:
n(int) : 입력받은 번째 숫자
memo(list, int) : 계산한 피보나치 순열 저장

풀이 방법:
메모이제이션 기법동일한 계산을 반복해야 할 경우 한 번 계산한 결과를 메모리에 저장해 두었다가 꺼내 씀으로써 중복 계산을 방지할 수 있게 하는 기법
재귀가 아닌 메모이제이션 기법을 사용하면 이미 계산해놓은 순열이 있어서 시간복잡도를 줄일 수 있음.

---

📑코드

def solution(n):

      memo=[0,1]
      for index in range(2,n+1):
        memo.append((memo[index-1]+memo[index-2])%1234567)
      return memo[n]

📝코드 설명
피보나치 순열은 0, 1, 1, 2, 3, 5, 8, 13, 21, ...로 앞과 그이전값을 더해서 새로운 값이 되는 순열이다. $n=(n-1)+(n-2)$
미리, 0, 1을 memo에 붙여 넣고 2부터 반복을 시작한다.
$n=(n-1)+(n-2)$을 계산한 값을 memo에 넣고 필요한 수를 인덱스로 가져온다.
🎖제출 결과

💡insight
재귀를 사용하면 시간초과 결과가 나온다.