피보나치 수

피보나치 수의 값을 구하고 1234567 로 나눈 나머지 결과 값을 구하는 문제!

 

우선 피보나치 수 라는 것은..

F(0)=0, F(1)=1 이며 1 이상의 n 에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 이다!

 

보통 피보나치 수열을 처음 코딩으로 배울때는 재귀함수가 많이 쓰이긴 하는데..

프로그래머스에서 재귀함수를 이용해서 풀면 '시.간.초.과' 에러가 난다..!

 

그래서 피보나치 수열의 특징을 살펴보니.. (Fibo 라고 부르겠답)

 

Fibo(7) 를 예시로 보면!

Fibo(7) = Fibo(6) + Fibo(5)

Fibo(6) = Fibo(5) + Fibo(4)

Fibo(5) = Fibo(4) + Fibo(3)

Fibo(4) = Fibo(3) + Fibo(2)

Fibo(2) = Fibo(1) + Fibo(0) = 1 + 0 = 1

 

이렇게 중간에 연산이 겹치는! 중복 연산의 부분이 꽤나 많이 발생한다

이렇게 되면 재귀함수로 풀었을때 더더욱 비효율 적인 것..!

 

이렇게 한번에 해결하기 힘든 문제들은 보통 "동적 계획법(Dynamic Programming)"을 이용해서 푼다고 한다

피보나치 수열의 경우 연산이 중복되지 않게 하면 되니까..

값을 배열에 저장해두는 Memozation 방식이 적당하다!

 

어려울건 없고, 큰 값을 구하기 위해선 작은 값이 모두 필요하니까~ 그냥 단순히 bottom-up 으로 작은 것 부터 계산하여 저장하면 된다!

 

최종 코드는 아래와 같다!

def solution(n):
    flist=[0,1] 
    
    for i in range(2,n+1):
        flist.append(flist[i-2]+flist[i-1])
        
    return flist[-1]%1234567

 

서론에 비해 코드가 참 별거 없다 

 

 

 

출처 : https://school.programmers.co.kr/learn/challenges