[Python] [Level 2] 피보나치 수 구현

https://school.programmers.co.kr/learn/courses/30/lessons/12945?language=python3 

프로그래머스

 

 

풀이 (1차 시도)

def fibonacci(m):
    if m == 1 or m == 2:
        return 1
    else:
        return fibonacci(m-1) + fibonacci(m-2)
    

def solution(n):
    answer = fibonacci(n)
    return answer

Or

def solution(n):
    if n == 1 or n == 2:
        return 1
    else:
        return solution(n-1) + solution(n-2)

 

 

재귀 함수로는 효율성 때문에 풀수 없다.

for 문을 사용해서 풀어야 한다.

 

힌트 내용

재귀 호출 대신 for문을 사용해서 첫 번째, 두 번째, 세 번째, ..., n번째 피보나치 수를 순서대로 구해보세요.
이러한 풀이 방식을 동적 계획법(Dynamic Programming)이라고 합니다.

 

풀이 (2차시도) 

def solution(n):
    a = 1
    b = 1
    if n == 1 or n == 2:
    	return 1
    for i in range(1, n):
    	a, b = b, b + a
    
    return a