[파이썬] 프로그래머 코딩테스트 - 피보나치 수 완벽해설 (효율성 고려)

문제

 

 

 

해설

 

 

https://vehiclewithai.tistory.com/41

[파이썬] 백준 연습문제 #11653. 골드바흐의 추측 완벽해설

 

이전에 피보나치 수에 대한 해설 글을 준비한 적이 있다. 그 당시에는 "재귀적 용법"을 사용하여 피보나치 수 코드를 짰는데, 이 경우 정말 비효율적으로 계산하게 된다.

 

fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)

위처럼 재귀적 용법을 사용하여 피보나치 수를 계산하게 되면 fibonacci(n-1)과 fibonacci(n-2) 안에 엄청나게 중복된 계산이 담겨있게 된다. 뿐만 아니라 fibonacci(n-1)은 또 fibonacci(n-2)+fibonacci(n-3)으로 나타나게 되는데 이 안에도 엄청나게 중복된 계산이 담겨있다.

 

이 중복된 계산으로 인해 n이 커짐에 따라 계산 시간이 기하급수적으로 늘어나게 되고, 심지어 메모리 초과로 인해 문제가 풀리지 않은 경우를 맞닥뜨릴 수도 있다.

 

따라서 이 중복된 계산을 모두 없애주어야 완전한 피보나치 수 풀이라고 할 수가 있다.

이 중복 계산을 해소하는 방법으로는 재귀적 용법을 아예 고려하지 않고, 피보나치 수를 한번의 계산으로 처음부터 누적해서 계산해주는 방법이 있다.

 

즉 

fibonacci[0] = fibonacci(0)

fibonacci[1] = fibonacci(1)

fibonacci[2] = fibonacci[1] + fibonacci[0]

fibonacci[3] = fibonacci[2] + fibonacci[1]

...

return fibonacci[n] = fibonacci[n-1]+fibonacci[n-2]

위처럼 피보나치에 대한 계산을 딱 한번만 해주도록 하나하나 차근차근히 계산하는 방식을 사용할 수 있다.

 

여기서 더 효율적으로 만들기 위해, 메모리를 더 아끼기 위해 "fibonacci"라는 리스트를 사용하지 않고, 임시 변수 tmp를 통해서 할 수도 있는데,

 

a = fibonacci(0)

b = fibonacci(1)

sum = a + b

a = b

b = sum

sum = a + b

a = b

b = sum

sum = a + b

...

sum = a+b

return sum

 

위와 같이 계산해주면 긴 리스트를 저장할 필요도 없어져서 더욱 효율적으로 알고리즘을 짤 수 있게 된다.

 

 

 

코드

 

 

def solution(n):
    if n==0:
        return 0
    elif n==1:
        return 1
    else:
        sum = 0
        a, b = 0, 1
        for i in range(n-1):
            sum = a+b
            a = b
            b = sum
        return sum % 1234567

 

 

결과