[BaekJoon] 백준 2748 피보나치 수 2 (Python / 파이썬)

BaekJoon 백준 2748 피보나치 수 2 문제는 피보나치 수는 0과 1로 시작하고, 다음 2번째부터는 바로 앞 두 피보나치 수의 합이 된다. n이 주어졌을 때, n번째 피보나치 수를 구하는 문제이다. 재귀와 메모이제이션 2가지 방식이 있다. 난이도는 Bronze 1이다.

 

BaekJoon 2748 피보나치 수 2 문제 정보

출처

- https://www.acmicpc.net/problem/2748

알고리즘 분류

- 동적 계획법 DP, 메모이제이션 memoization

난이도

- 브론즈 1 / Bronze 1

 

피보나치 수 2 문제 요약

• 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다.
• 그다음 2번째부터는 바로 앞 두 피보나치 수의 합이 된다.
• 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.
• 90보다 작거나 같은 자연수 n이 주어졌을 때, n번째 피보나치 수를 구하여 출력한다.

 

문제 풀이 과정

1. 메모이제이션 기법을 사용하여 함수의 결과 값을 저장해 놓기 위해 memo 리스트를 선언한다.
2. f(0) = 0, f(1) = 1 이므로 memo [0] = 0, memo [1] = 1을 저장한다.
3. 피보나치수열 함수를 정의한다.
4. 만약 memo 리스트의 길이가 n보다 크면 memo [n]에 fibo(n)의 값이 저장되어 있는 것이므로 memo [n]을 리턴한다.
5. 아니면 memo리스트에 저장되어 있지 않는 값이므로 memo [n]에 n의 피보나치 수를 구하여 저장하고 memo [n]을 return 한다.
6. n번째 피보나치 수를 출력한다.

 

코드 및 설명

def fibo(n):
    global memo
    if n < len(memo):
        return memo[n]
    else:
        memo.append(fibo(n - 1) + fibo(n - 2))
        return memo[n]


memo = [0, 1]
print(fibo(int(input())))

 

피보나치 수를 구하는 방법은 대표적으로 재귀 함수를 사용하는데, 이는 엄청난 중복 호출이 발생하기 때문에 시간이 오래 걸리고 백준 2748번 문제의 경우에는 시간 초과가 발생합니다.

 

이러한 재귀 함수의 단점을 보완한 프로그래밍 기법이 바로 메모이제이션 기법인데요, 성능, 실행 속도 향상을 위해 중요한 기술이므로 한 번 읽어보시면 큰 도움이 될 것입니다.

 

메모이제이션(Memoization) 개념 및 예시, 재귀(recursion)

메모이제이션(Memoization) 개념 및 예시, 재귀(recursion)

---

BaekJoon 백준 2748 피보나치 수 2 문제를 파이썬 python으로 memoization 메모이제이션 기법을 사용하여 풀어보았다. 난이도는 Bronze 브론즈 1이다.