피보나치 알고리즘과 메모이제이션 (with Python3)

피보나치 알고리즘

피보나치(Fibonacci) 수열은 첫번째와 두번째 원소가 0 과 1이고, 세번째 원소부터는 이전 원소 두 개의 합인 수열을 말한다.

 

예를들어,

0, 1, 1, 2, 3, 5, 8, 13, 21, ...

 

Python3 코드

아래 코드는 unittest 기반으로 작성했다. 전체 로직은 fibo() 메소드를 참고한다.

# -*- coding: utf-8 -*-

import unittest


class Exam06(unittest.TestCase):

    @classmethod
    def setUp(cls):
        pass

    def fibo(self, k):
        if k == 1:
            return 0
        elif k == 2:
            return 1
        return self.fibo(k-1) + self.fibo(k-2)

    def test_fibonacci(self):
        self.assertEqual(0, self.fibo(1))
        self.assertEqual(1, self.fibo(2))
        self.assertEqual(1, self.fibo(3))
        self.assertEqual(2, self.fibo(4))
        self.assertEqual(3, self.fibo(5))
        self.assertEqual(5, self.fibo(6))
        self.assertEqual(8, self.fibo(7))


if __name__ == "__main__":
    unittest.main()

k 가 1일때는 0, 2일 때는 1로 미리 정의한다. 그 이후부터는 재귀함수를 이용하여 결과값을 반환한다.

 

메모이제이션

위 코드에서 n 값을 작게 했을때는 문제가 없지만, 숫자가 커질수록 연산 속도가 급격히 낮아진다.

 

예시로 35번째 원소를 구해보자.

import time

def fibo(k):
    ....
    
start = time.time()
fibo(35)
end = time.time()
print("수행 시간: {}".format(end - start))

수행 시간: 2.8540451526641846

고작 35번째 값을 구하는데 2.85초나 걸렸다. (해보면 알겠지만 100번째 원소를 구하려고 하면 끝나지도 않는다. 한번 해보고 얼마나 걸리는지 알려주세요)

 

이때, 메모이제이션을 이용한다.

메모이제이션(Memoization)은 이미 연산한 값은 저장공간에 저장하여, 두번 이상 연산하는 일이 없도록 해준다.

 

Python3 코드

마찬가지로 unittest 기반으로 작성했다. 전체 로직은 fibo_memo() 메소드를 참고한다.

# -*- coding: utf-8 -*-

import unittest


class Exam06(unittest.TestCase):
	
    ...
    
    def fibo_memo(self, memo, k):
        # 이미 계산한 적이 있는 값
        if memo[k] != -1:
            return memo[k]

        # 처음 계산하는 값
        if k == 1:
            memo[k] = 0
        elif k == 2:
            memo[k] = 1
        else:
            memo[k] = self.fibo_memo(memo, k-1) + self.fibo_memo(memo, k-2)
        return memo[k]

    def test_with_memoization(self):
        memo = [-1, -1, ]
        self.assertEqual(0, self.fibo_memo(memo, 1))

        memo = [-1, -1, -1, ]
        self.assertEqual(1, self.fibo_memo(memo, 2))

        n = 35
        memo = [-1 for _ in range(n + 1)]
        self.assertEqual(5702887, self.fibo_memo(memo, n))

        n = 50
        memo = [-1 for _ in range(n + 1)]
        self.assertEqual(7778742049, self.fibo_memo(memo, n))

        n = 100
        memo = [-1 for _ in range(n + 1)]
        self.assertEqual(218922995834555169026, self.fibo_memo(memo, n))


if __name__ == "__main__":
    unittest.main()

n 값을 35, 50, 100 처럼 큰 수를 넣어서 계산을 해도 바로 연산되어 값을 반환한다.

 

위 테스트 케이스를 모두 수행하는데 단 0.002초 밖에 안걸린다.

결론

피보나치 수열을 작성할때는 반드시 메모이제이션을 사용하자. n 이 조금만 커져도 수행 속도가 급격히 느려진다.

Reference

• https://thebook.io/006935/part02/ch05/02-05/