[프로그래머스] 피보나치 수(python)

프로그래머스, 피보나치 수

 

TL;DR

• 재귀(Recursive) 또는 동적 프로그래밍(Dynamic programming)을 활용할 수 있는지

문제 분석

1. 2 이상 n 이하의 주어진 입력에 따라 피보나치 코드를 완성하라.
2. 완성된 피보나치 수는 1234567로 나눈 나머지를 리턴해야 한다.

 

- 1 : 해결해야 하는 문제 조건을 알려주고 있다.

- 2 : 구한 피보나치 수를 1234567로 나눈 나머지로 구해야 한다.

입출력 형태

입출력 예시

 

- 주어진 n번째 피보나치 수를 구하면 된다.

- 문제 조건 2에 따라서 각 피보나치 수는 1234567로 나눈 나머지를 반환해야 한다.

- 이 이유는 피보나치 수가 n에 따라서 점점 많이 커지기 때문에 표현할 수 있는 범위를 넘어갈 수 있기 때문이다.

풀이

def solution(n):
    FIBO = [0, 1] + [0] * (n - 1) # 메모이제이션
    if n == 0 or n == 1:
        return FIBO[n]
    
    for i in range(2, n + 1): # 바텀-업 방식 사용
        FIBO[i] = FIBO[i - 1] % 1234567 + FIBO[i - 2] % 1234567

    return FIBO[n] % 1234567

 

- 익히 알려진 재귀 방식으로 풀 수 있지만, 동적 프로그래밍, 그 중에서도 바텀-업 방식을 사용하여 해결하였다.

- 주어진 n만큼 피보나치 수를 저장할 배열 FIBO를 선언한다.

- n이 0과 1이 주어졌을 때는, 0과 1을 반환하도록 한다.

- 2부터 n까지 증가하며, 각 피보나치 수를 만들어 배열 FIBO에 저장한다.

   - 이 때, 각 배열 또한 1234567로 나눈 나머지를 저장해야 한다.

   - 합을 한 이후 1234567로 나누지 않는 이유는, 덧셈이 먼저 진행되고 나면 올바른 답이 나오지 않기 때문이다.

- 계산된 n번째 피보나치 수를 1234567로 나눈 나머지를 반환한다.

 

다른 풀이

- 동적 프로그래밍의 탑-다운 방식으로도 풀 수 있고, 재귀 호출 방식으로도 풀 수 있다.