[동적 계획법] 백준 24416 알고리즘 수업 - 피보나치 수 1 (Python 파이썬)

💡문제 링크

https://www.acmicpc.net/problem/24416

 

💡문제 분석 요약

피보나치 수열을 재귀함수로 푸는 의사 코드, 동적 계획법으로 푸는 의사 코드가 주어졌다.

이를 실제 파이썬 코드로 바꾸고, 연산횟수를 출력하여라.

 

💡알고리즘 설계

1. 재귀함수 코드 짜기

2. DP 코드 짜기

3. 함수 안에 변수를 넣을 때 global 함수 써주기 ⭐ ⭐ ⭐

 

💡코드

n = int(input())
count_recur, count_dp = 0, 0
f = [0] * (n+1)

def fib_recur(n):
  global count_recur 
  if (n==1 or n==2):
    count_recur += 1
    return 1
  else:
    return fib_recur(n-1) + fib_recur(n-2)

def fib_dp(n):
    global count_dp
    f[1], f[2] = 1, 1
    for i in range(3, n+1):
        count_dp += 1
        f[i] = f[i-1] + f[i-2]
    return f[i]

fib_recur(n)
fib_dp(n)
print(count_recur, count_dp)

 

💡 오답 풀이

처음에 연산횟수를 세는 count += 1 코드를 어디에 넣어야할지 잠시 헤맸다. 그래서 종이에 직접 써가면서 했다!

계속 시간초과 떠서 결국 구글링했는데,

Python3 말고 PyPy3로 언어를 바꿨더니 통과되었다는 글을 보았다.

나도 PyPy3로 바꿔봤는데, 바꾸니까 바로 통과되었다.

왜 PyPy3로 통과되었을까?

1. 재귀 깊이: PyPy3는 재귀 호출의 처리 성능이 뛰어나므로, 재귀 깊이가 깊은 피보나치 수열 계산 같은 문제에서 CPython보다 더 효율적이다.
2. 속도: PyPy3의 JIT 컴파일러 덕분에 계산 속도가 빨라져서 시간 제한을 초과하지 않았을 가능성이 높다.
3. 메모리 관리: PyPy3의 메모리 관리가 더 효율적이라, 메모리 부족 문제로 인한 실패를 피할 수 있었을 것이다.

💡 다른 풀이

...

 

💡 느낀점 or 기억할정보

Python3

• CPython 인터프리터: Python3는 CPython이라는 표준 인터프리터를 사용합니다. 이는 C로 구현되어 있으며, 가장 널리 사용되는 Python 인터프리터입니다.
• 속도: CPython은 일반적으로 속도가 느린 편입니다. 특히, 재귀 호출이나 복잡한 계산 작업에서는 성능이 좋지 않을 수 있습니다.
• 메모리 관리: CPython은 메모리 관리를 비교적 보수적으로 수행합니다.

PyPy3

• JIT 컴파일러: PyPy3는 Just-In-Time (JIT) 컴파일러를 사용합니다. 이는 코드 실행 중에 부분적으로 컴파일을 수행하여 성능을 크게 향상시킵니다.
• 속도: PyPy3는 CPython보다 일반적으로 훨씬 빠릅니다. 특히, 반복적인 계산이나 재귀 호출이 많은 코드에서 큰 성능 향상을 제공합니다.
• 메모리 사용: PyPy는 메모리를 더 효율적으로 사용할 수 있습니다.