[프로그래머스] 피보나치 수Lv.2 - Python

[프로그래머스] 피보나치 수Lv.2

나의 풀이

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

• 이미 했던 연산을 반복할 필요 없이 d 리스트에 연산 결과를 저장하게 하였다. 이렇게 반복적이거나 큰 문제에서 작은 문제의 결과를 그대로 이어서 쓸 때는 다이나믹 프로그래밍으로 접근하면 시간 복잡도를 극단적으로 낮출 수 있다.

느낀점

피보나치 수 까지만 보면 다이나믹 프로그래밍을 이해한 것 같은데 이 이상의 문제를 만나면 다이나믹 프로그래밍으로 접근하는 것이 매우 힘들다.