08.19. 프로그래머스 : 피보나치 수

🔎 피보나치 수

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

피보나치 수란?
자기자신보다 앞에 있는 두 숫자를 더하면 자신이 된다. 피보나치 수는 아래와 같다.
F = [ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ... ]

F[3] 에 위치한 2는 F[1] 과 F[2]에 위치한 수 1과 1의 합이 됨을 확인할 수 있다.
F[3] = F[1] + F[2]
2 = 1 + 1

피보나치를 식으로 나타내면 아래와 같다.
 F(n) = F(n-1) + F(n-2)

수학적으로 피보나치에서 F(1)과 F(2)는 1이다.
F(0) = 0, F(1) = 1

💡 문제풀이#1 (실패)

def solution(n):
    # n번째 피보나치 수열 : F(n) = F(n-1) + F(n-2) 
    save_fib = []
    if n in [0, 1]:
        save_fib.append(1)
    else:
        for num in range(2, n - 1):
            n_fib = (num - 1) + (num - 2)
            save_fib.append(n_fib)
    return n_fib % 1234567

n의 값이 답이 아니라, n번째에 위치하는 피보나치 수열이 도출되어야 하는 문제인데, 이 부분을 정확하게 이해하지 못해서 생긴 문제풀이이다. 

💡 문제풀이#2 (실패)

def solution(n): 
    save_fib = [0, 1]
    
    for i in save_fib:
        fib = save_fib[i] + save_fib[i + 1]
        save_fib.append(fib)
        ...

save_fib의 길이를 기준으로 하여서 save_fib에 append할때마다 늘어나는 길이가 반영될까..? 하고 짜봤는데, for문이 처음 시작된 그 길이에서 고정이 되기 때문에 이렇게도 풀 수 없다.

💡 문제풀이#3 (성공)

'''
1. 첫번째 연산을 시킬 수 있는 수가 있어야 한다. 
	- save_fib에다가 0, 1을 먼저 넣어놓자.
    
2. save_fib[0] save_fib[1] = f[2] == 1
    
3. 1 추가해준다
    
4. save_fib[0, 1, 1] save_fib[1] save_fib[2] == f[3] == 2
    
5. 2 추가해준다
    
결론 : 'index' 로 불러와야 한다. 
'''

함수 구현 방향을 글로 다시 정리해봤다. 2, 4번을 쓰면서 2번 문제풀이에서 잘못된 for문의 범위, 그리고 index를 사용해야 한다는 것을 깨달았다.

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

n번째 피보나치 수를 구하는 문제이므로 약 n번의 피보나치 수 계산 함수가 작동해야 한다. for문의 range에 n을 넣어준다. 그리고 피보나치의 식을 사용할 때 n - 1, n - 2 는 n, n + 1 과 같다.

💡 추가개념

피보나치 수는 대표적인 동적 프로그래밍의 사례이다.

▶ 동적 프로그래밍 :  큰 문제의 해답에 그보다 작은 문제의 해답이 포함되어 있을 때, 속도를 비약적으로 향상시킬 수 있다.

# 기본 피보나치 수열
def solution(n):
    if n == 1 and n == 2:
        return 1
    return solution(n - 1) + solution(n - 2)

위의 기본 식은 n이 100 이상의 아주 큰 숫자들이 입력되었을 때 처리시간이 굉장히 느리다.

이는 피보나치 수의 중복호출 문제 때문이다.

함수를 실행하다보면 이렇게 겹치는 숫자들이 생긴다. 2n번만큼의 계산이 필요하다. (이는 지수함수로 표현할 수 있다. 지수함수는 가파르게 증가한다.) 컴퓨터에서는 이런 지수 함수는 현실적으로 문제를 풀 수 없는 문제이다.

바로 여기에서! 동적 프로그래밍 작업이 필요하다.

def Fibonacci(n):
    # 10번째 위치까지의 F를 구해서 append 해준다. 만약 n이 F 안에 있다면 그 값을 return 해준다.

    F = [0, 1]
    if n in F:
        return F[n]
    else:
        for i in range(2, n):
            fib = F[i - 1] + F[i - 2]
            F.append(fib)
            print(F)

Fibonacci(100)  
# 피보나치 수열의 100번째에 위치한 값이 답이 된다.
# 굉장히 빠르게 구할 수 있다.

함수를 통해 계산한 값을 F에 저장해준다. 만약 n이 F 안에 있다면 F에 들어있는 그 값을 return 해준다면, 값을 구했던 식을 또 구하지 않아도 되기 때문에 연산 속도가 폭발적으로 증가한다.

 

정말 어렵고 헷갈리는 문제였지만 정리하면서 굉장히 많은 공부가 되었다.
비슷한 문제를 만날때마다 이 글을 다시 확인하면서 점점 익혀나가면
언젠가는 나 스스로 쉽게 이 문제를 풀 수 있겠지!!

 

 

 

** 다음에 재귀로도 한번 풀어보자!

https://richwind.co.kr/3