백준 24416번_알고리즘 수업 - 피보나치 수 1 (Python)

문제 바로가기

 

백준 내 동적 계획법 1단계를 하나하나 풀어가려고 한다.

 

문제

오늘도 서준이는 동적 프로그래밍 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자.

오늘은 n의 피보나치 수를 재귀호출과 동적 프로그래밍으로 구하는 알고리즘을 배웠다. 재귀호출에 비해 동적 프로그래밍이 얼마나 빠른지 확인해 보자. 아래 의사 코드를 이용하여 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];
}

 

풀이

조금 불안했지만 무작정 두 의사 코드를 파이썬 함수로 바꾸어서 돌려보았고, 예상대로 시간 초과가 났다. 이 문제는 수학적으로 두 코드의 실행 횟수를 계산해야한다.

fib(n)을 돌렸을 때 코드1이 수행되는 횟수를 count1(n), fibonacci(n)을 돌렸을 때 코드2가 수행되는 횟수를 count2(n)으로 두자.

 

1. count1

count1(1)과 count1(2)는 둘다 1인 것을 쉽게 알 수 있다. 여기서 count1(1) = fib(1), count1(2) = fib(2)인 것도 확인할 수 있다. 여기서 수학적 귀납법을 사용할 것이다.

임의의 자연수 k>=3에 대해 count1(k-1) = fib(k-1), count1(k-2) = fib(k-2)가 성립한다 하자.

fib(k)이 실행되는 과정을 보자.

fib(k) {
    if (k = 1 or k = 2) # k는 3 이상이므로 else로 건너뜀
    then return 1;  # 코드1
    else return (fib(k - 1) + fib(k - 2)); # fib(k-1)과 fib(k-2)가 순서대로 실행됨
}

fib(k-1)에서 count1(k-1)번, fib(k-2)에서 count1(k-2)번 코드1이 실행된다. fib(k)안에서 if문을 건너뛰었기에 이외의 추가적인 코드1의 실행은 존재하지 않는다.

따라서 fib(k)을 실행하면 총 count1(k-1) + count1(k-2) 번 코드1이 실행된다.

즉, count1(k) = count1(k-1) + count1(k-2)이고, 여기서 count1(k-1) = fib(k-1), count1(k-2) = fib(k-2)이므로

count1(k) = fib(k-1) + fib(k-2) = fib(k)

따라서 임의의 자연수 n에 대해 count1(n) = fib(n)이 성립한다.

(fib(n)은 효율적인 동적 계획법으로 만든 피보나치 함수 fibonnaci(n)으로 대신 구할 수 있다.)

 

2. count2

fibonnaci는 동적 계획법(Dynamic Programming)을 사용한 함수다. 즉, 배열 f에서 f[n]의 자리에 n번째 피보나치 수를 저장해서 앞의 계산을 반복하지 않게 한다. 어렵게 따질 필요도 없이 for문이 보이고, 그 안에 코드 2가 있다. i가 3부터 n까지 변하면서 for문이 실행되므로, fibonnaci(n)에서 코드2는 총 n-2번 실행된다.

따라서 임의의 자연수 n에 대해 count2(n) = n-2이 성립한다.

 

코드

f = [None]*50
f[1] = f[2] = 1

n = int(input())

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

count1 = fibonacci(n)
count2 = n-2
print(k1, k2)