[Python] 피보나치(Fibonacci) 수열 aka 점화식

Dynamic Programming(DP)로도 불린다. 도르마무같은...

 

피보나치(Fibonacci) 수열

def solution(n):
	a, b = 0, 1
    
    for _ in range(n+1):
    	a, b = b, a+b
 
    return a

기본 형태는 위와 같으며 a, b의 값을 변경하거나 추가적인 구문을 넣어 활용할 수 있다.

요새 누르는 족족 점화식 문제가 날 반겨준다.

인공지능형 카페 창업을 생각중이다.

 

---

[프로그래머스 Lv2] 멀리 뛰기

https://school.programmers.co.kr/learn/courses/30/lessons/12914

프로그래머스

1을 이동할경우 -> [1]

2를 이동할경우 -> [1, 1], [2]

3을 이동할경우 -> [1, 1, 1], [2, 1], [1, 2]

F(1) -> 1

F(2) -> 2

F(3) -> 3 임을 알 수 있다.

 

따라서 점화식을 이용하여,

def solution(n):
    a, b = 0, 1
    
    for _ in range(n):
        a, b = b, (a+b) % 1234567
    return b

 

또는,

def solution(n):
    a, b = 1, 1
    
    for _ in range(n):
        a, b = b, (a+b) % 1234567
    return a

로 풀어볼 수 있다.

 

본래라면 F(1) -> 1, F(2) -> 1, F(3) -> 2가 나와야하지만

문제에서는 F(n+1)의 값이 해답이기 때문이다.