[프로그래머스] 피보나치 수(Python)

💻 문제 - Lv.2

👉 제출 코드

일반 재귀로 하면 시간초과가 발생한다

쓰이는 게 또 쓰이는 재귀 대신, DP를 사용한다

동적 계획

작은 문제를 해결한 뒤, 이를 이용해 큰 문제를 비교적 간단하게 해결

def solution(n):
    dp = [-1] * (n+1)
    dp[0] = 0
    dp[1], dp[2] = 1, 1
    for i in range(3, n+1):
        dp[i] = dp[i-2] + dp[i-1]
    return dp[n]%1234567

바텀업인, Tabulation을 사용하여 풀이했다: for문을 사용해서 전에 쓰였던 값을 배열에 저장한다

• dp의 길이는 n이면 안된다 -> n+1 이상

🙏 다른 사람의 풀이 보기

def fibonacci(num):
    answer = [0,1]

    for i in range(2,num+1):
        answer.append(answer[i-1]+answer[i-2])
    #print(answer)

    return answer[-1]

• 리스트는 가변한다는 것을 사용하여 길이를 지정하지 않고 append()를 사용한다
• 인덱스를 -1로 접근한다