[알고리즘] 프로그래머스 | 피보나치 수열

피보나치 수열이란?

수학에서 피보나치 수(영어: Fibonacci numbers)는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다.

처음 여섯 항은 각각 1, 1, 2, 3, 5, 8이다. 편의상 0번째 항을 0으로 두기도 한다

 

 

프로그래머스 문제에 의하면 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수를 말한다

다음 수를 만들때 이전 수와 자기자신을 더하는 방식이므로 재귀가 가능하다!

 

 

 

 

문제를 풀기 전에 피보나치 수열을 구하는 7가지 방법을 알아보자!

 

•  1) 일반 함수 구현
•  2) 재귀 함수 구현
•  3) 제네레이터 (Generator) 방식
•  4) 메모이제이션 (Memoizatioin) 방식
•  5) 파이썬 한줄 코딩 (Single Line) 1
•  6) 파이썬 한줄 코딩 (Single Line) 2
•  7) 파이썬 행렬 연산 (Numpy) 

 

 

 

1) 일반 함수 구현 (수열을 구함)

[ fib(x) for x in range(1,10) ]

 

2) 재귀 함수 구현

def fibo(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

 

3) 제네레이터 (Generator) 방식

def fibo():
    a,b = 0,1    
    while True:
        a,b = b, a+b
        yield a

 

4) 메모이제이션 (Memoizatioin) 방식

def fibo(n):
    fibList=[1, 1]
    if n==1 or n==2:
        return 1
    for i in range(2,n):
        fibList.append( fibList[i-1] + fibList[i-2] )
    return fibList

 

5) 파이썬 한줄 코딩 (Single Line) 1

fibo = lambda n: 1 if n<=2 else fibo(n-1) + fibo(n-2)

 

6) 파이썬 한줄 코딩 (Single Line) 2

fibo = lambda n, a=0, b=1 : a if n<=0 else fibo(n-1,b, a+b)

 

7) 파이썬 행렬 연산 (Numpy) 

A = np.matrix( [ [1,1], [1,0] ] )

(A**5)[0,1]

 

 

 

자세한 설명은 생략한다!

 

[참고] : 파이썬으로 피보나치 수열을 구하는 7가지 방법  https://richwind.co.kr/3

 

 

 

---

피보나치 수열

답: 

def fibo(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


def solution(n):
    return fibo(n) % 1234567

함수 재귀로 풀면 아쉽게도 런타임 에러와 시간초과가 난다ㅠ.ㅠ

 

 

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

 

def solution(n):
    answer = [0, 1]
    for i in range(n):
	    fib = answer[i] + answer[i+1]
	    answer.apppend(fib)
    return answer[n] % 1234567

 

 

문제 분석 및 해석

2 이상의 n이 입력되었을 때,

n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수,

solution을 완성

 

>> 풀이생각

숫자 n = n번째 피보나치수를 구하기

(n-1) + (n-2)

해당 수를 1234567로 나눈 나머지 리턴하기

fibo 함수를 작성해서 구한 수를 %로 나누자!

 

 

# fibo =  [0, 1, 1, 2, 3, 5, 8, 13...] 이므로 2를 집어넣으면 1번째 index의 수인 1을 get

# 3이면 2니까 2 index 위치임!

 

 

 

리뷰.

피보나치 수열을 구하는 방법만 알면 쉽게 풀이할 수 있는 문제였다.

마냥 재귀함수로 풀이할 생각만 했는데 런타임 에러가 나서 당황..

재귀로 풀릴줄알았는데 아쉽

 

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

 

for 문으로 변경하고 스스로와 이전 수를 저장해뒀다 더해, 재할당해주는 식으로 풀이했다.

def fibo(n):
    a = 1
    b = 1
    ...
    for i in range(1, n):
    # 자기 자신과 그 이전 수를 더하는 것을 반복하여 다음 수를 구함
    	a, b = b, b + a
    return a