[백준] 24416. 알고리즘 수업 - 피보나치 수 1 (파이썬 python, pypy3)

 

다이나믹 프로그래밍 문제를 좀 더 풀어보고 싶어서 좀 더 어려운 문제를 풀어보았다. 

 

 

문제

 

아래 의사 코드를 이용하여 n의 피보나치 수를 구할 경우 코드1 코드2 실행 횟수를 출력하자.

 

피보나치 수 재귀호출 의사 코드는 다음과 같다.

fib(n) {
    if (n = 1 or n = 2)
    then return 1;  # 코드1
    else return (fib(n - 1) + fib(n - 2));
}

 

피보나치 수 동적 프로그래밍 의사 코드는 다음과 같다.

fibonacci(n) {
    f[1] <- f[2] <- 1;
    for i <- 3 to n
        f[i] <- f[i - 1] + f[i - 2];  # 코드2
    return f[n];
}

 

입력

첫째 줄에 n(5<= n <= 40) 이 주어진다.

 

출력

코드1 코드2 실행 횟수를 한 줄에 출력한다. 

 

---

 

백준 24416 해설

 

백준 24416 정답 코드 1 (pypy3)

#다이나믹 프로그래밍
num = int(input())
f = [0]*(num+1)
fib_count = 0
fibo_count = 0

#피보나치 재귀호출
def fib(n):
    global fib_count
    
    if n == 1 or n == 2:
        return 1;  # 코드1
    else:
        fib_count += 1
        return (fib(n - 1) + fib(n - 2))

#피보나치 동적 프로그래밍
def fibonacci(n):
    global fibo_count
    f[1], f[2] = 1, 1
    for i in range(3,n+1):
        f[i] = f[i - 1] + f[i - 2]  # 코드2
        fibo_count += 1
    return f[n]

fib(num)
fibonacci(num)

print("%d %d" % (fib_count+1,fibo_count))

 

처음 python3로 제출했을 때는 시간 초과가 일어나서 pypy3으로 다시 제출하고 나서야 맞았다. 코드가 마음에 들지 않아서 다시 제출해야지 하는 생각을 가지고 있었다.

 

 

 

 

백준 24416 정답 코드 2 (python)

#다이나믹 프로그래밍
num = int(input())

#피보나치 재귀호출
def fib(n):
    f = [0] * (n+1)
    f[1], f[2] = 1 ,1
    for i in range(3, n+1):
        f[i] = f[i - 1] + f[i - 2]
    return f[n]
    

#피보나치 동적 프로그래밍
def fibonacci(n):
    return n - 2



print("%d %d" % (fib(num),fibonacci(num)))

 

피보나치 재귀호출 횟수를 동적 프로그래밍으로 구할 수 있다. 이 방법을 사용해 시간을 많이 줄일 수 있었다. 

 

피보나치 동적 프로그래밍 횟수는 굳이 함수로 시간을 재지 않아도 n - 2번이라는 공식을 구할 수 있었기 때문에 그냥 값을 리턴하도록 만들었다. 

 

 

 

---

 

결과 & 느낀점

 

한 문제를 수정해서 다시 풀어보니 좋았다. 

피보나치 수를 구하면서 함수의 실행횟수를 구하는 것보다, 실행횟수가 n과 어떤 관계가 있는지 알아내고 함수를 계산하는게 더 빠른 길이었다. 다음에는 문제에 주어진 대로 따라가지 말고 어떤 방법이 더 효율적인지 생각해 보는 시간을 오래 가져야겠다. 

 

pypy3이란 언어도 처음 알게 되었는데 파이썬보다 실행 시간이 적게 걸리는 언어인가보다. 파이썬과 어떤 차이가 있는지 자세히 알아보고 싶다.