피보나치 수열로 알아보는 알고리즘 최적화

프롤로그

IT 업계에서 근무하면서 느끼는 건 개발자 수준에 따라 같은 문제를 참 다양한 방식으로 푼다는 것이다. 내가 풀었을 때는 수행시간이 3분인데, 또 내 선임이 손 대면 3초로 끝나는 마법!

왜 그러는 것일까? 그냥 내가 단순 무식하게 빨리 일을 끝내려고 해서 그런건 아니였을까?

피보나치 수열을 다양한 방식을 적용하여 풀어보고 수행시간 변화를 확인해 보자.

피보나치 수열이란?

고등학교 1학년 수학시간에 배우는 피보나치 수열은 너무나 유명한 '수'이다.

제 0항을 0으로, 제 1항을 1로 두고, 둘째 번 항부터는 바로 앞의 두 수를 더한 수로 놓는다. 이를 점화식 형태로 표현하면 다음과 같다.

$F_{0} = 0,\quad F_{1} = 1$

$F_{n+2} = F_{n+1} + F_{n}$

재귀적으로 풀기

재귀적인 풀이는 위의 점화식 정의를 충실히 따른다. 수학적인 반복관계를 그대로 구현하면 된다.

def fibonacci(n)
	if n > 2:
    	return n
    else
    	return fibonacci(n-1) + fibonacci(n-2)

위 방법은 매우 간단 하지만 실용적이지는 않은데, 너무 느리기 때문이다. n=100만 넣어도 원하는 시간에 답을 구할 수 없다. 그 이유는 지속적인 반복 호출 때문인데, 재귀 트리를 그려보면 그 이유를 알 수 있다. 그림을 보면 fibonacci(5)를 계산 하기 위해 fibonacci(3)은 두번 호출되었고, fibonacci(2)는 세번 호출된다. 그리고 fibonacci(1)은 5번이나 호출되는 것을 알 수 있다.

재귀 트리에서 하나의 노드 당 2개씩 자식 노드가 증가하고 있음을 주목해야 한다.
n번 호출하면, $2^{n}$ 번씩 호출되는 것이다. 이를 $Big-O$ 표기법으로 표시하면 $O(2^{n})$이 되고, 이 함수의 수행속도는 n 이 증가 함에 따라 급격히 느려질 것이다.

그럼, n=100일때 몇 번 호출 될까? $2^{100}$ 을 계산해 보면 126,7650,6002,2822,9401,4967,0320,5376 된다. 나는 이 수를 어떻게 읽어야 하는지도 모르겠다.

우리는 정말 n=100 도 못구하는 풀이를 풀었다고 할 수 있을까?

동적 계획법 적용하기

단순 재귀적 풀이는 반복 호출이 문제였다. 답을 구하기 위해서 했던 계산을 또 하고 또 하고 계속해야 한다면, 전에 했던 계산을 저장해 놓으면 되지 않을까?

동적 계획법은,
동일한 계산을 반복해야 할 경우 한 번 계산한 결과를 메모리에 저장해 두었다가 꺼내 쓰는 것이다. 그래서 "컴퓨터 과학이 여는 세계"에서 이광근 교수는 동적 계획법을 기억하며 풀기로 표기하였다.

하향식으로 접근하기

동적 계획법에는 하향식 접근과 상향식 접근법 두가지가 있는데, 먼저 하향식 접근법을 적용해 보자. 하향식 접근은 위에서 아래로 가는 것이다. $F_{n}$을 구하기 위해서 $F_{n-1}$ 부터 $F_{0}$ 까지 n을 감소 시켜가는 것이 하향식 접근이다.

def fibonacci(n)
	if n > 2:
    	return n
    else
    	return fibonacci(n-1) + fibonacci(n-2)

재귀적 풀이를 보면 fibonacci(n) 을 구하기 위해 fibonacci(n-1), fibonacci(n-2)를 지속적으로 호출하고 있다. n을 감소시키면서 호출하고 있다. 이는 하향식 접근을 따르는 풀이이고, 반복 호출 문제를 가지고 있다.

이 문제를 해결하기 위해 fibonacci(i)를 계산 할 때 마다 dictionary 타입 변수 cahce에 저장한다. 그리고 필요할 때 그 값을 꺼내서 사용하도록 한다.

def fibonacci(n) -> int:
    cache = {0:0, 1:1}

    def fibonacci_inner(n):
        if n in cache:
            return cache[n]
        else:
            cache[n] = fibonacci_inner(n-1) + fibonacci_inner(n-2)
        return cache[n]

    return fibonacci_inner(n)

동적 계획법을 사용한 풀이의 재귀 트리를 그려보면 아래와 같다.(사각형으로 표시된 부분은 캐시값을 그대로 사용하는 경우이다.)

노드의 개수가 수행시간이 되는데, 각 노드의 자식 노드는 한 개 이므로 N에 대한 총 노드의 개수는 대략 $2\times n$가 된다. 따라서 수행 시간을 $Big-O$표기 법으로 표현하면 $O(n)$이 된다.

n=100을 넣어보면 성능이 얼마나 개선되었는지 알수 있는데,
재귀적인 풀이와 다르게 결과 값를 바로 리턴하는 것을 확인 할 수 있다. 수행 시간 $O(n)$ 과 $O(2^{n})$은 엄청난 차이가 있음을 체감할 수 있다.

상향식으로 접근하기

상향식 접근은 아래에서 위를 향해가는 것이다. $F_{n}$을 구하기 위해서 $F_{0}$에서 부터 n을 증가시켜 가는 것이다.

피보나치 점화식에서, $F_{0} = 0,\quad F_{1} = 1$ 이라 정의한 것을 기억하자. 이 둘을 이용해서 $F_{2}$를 계산하고, 차례로 $F_{3}, \quad F_{1}$ 등을 이전의 결과를 이용해 계산한다.

def fibonacci(n):
    fib_n = 0 # fibonacii(0)
    fib_n_plue_1 = 1 # fibonacii(1)
    fib_n_plue_2 = 0 # fibonacii(n+2)
    
    if n < 2:
        return n

    for i in range(2,n+1):
        fib_n_plue_2 = fib_n_plue_1 + fib_n
        fib_n = fib_n_plue_1
        fib_n_plue_1 = fib_n_plue_2 
    return fib_n_plue_2

상향식 접근법의 수행 시간 for문이 하나으로 $O(n)$이 되고, iterative 한 풀이와 완벽하게 같다.

행렬과 분할 정복법 적용하기

분할 정복법을 사용하기 위해서, 피보나치 수열의 점화식을 행렬의 곱으로 표현해 보자.

행렬의 곱을 풀어보면 점화식과 동일하게 됨을 확인 할 수 있는데, 위의 식은 아래와 같이 표현이 가능하다.

$F_{n+1}$ 와 $F_{n}$을 $F_{1}$ 와 $F_{0}$ 까지 확장시켜보면 아래의 식 형태가 되고

$\begin{pmatrix}1 & 1 \\1 & 0\end{pmatrix}^{n}$ 행열의 제곱을 풀어보면 결국 $a_{1,1}$ 원소는 $F_{n}$과 같음을 확인 할 수 있다.

결국, 행렬의 제곱으로 표현된 피보나치 수열의 관계식을 갖게 된다.

이제 우리는 $if\quad n>2$일 때, M=[[1,1],[1,0]] 의 거듭 제곱한 결과의 M[0][0] 을 리턴하기만 하면 된다.

일단 가장 익숙한 interative 한 방법으로 풀면, 반복문 하나 사용되고 이 풀이의 수행시간은 $O(n)$이 된다.

def fibonacci(n):
    M=[[1,1],[1,0]]
    F = [[1,1],[1,0]]
    if n==0:
        return 0
    if n == 2 or n == 1:
        return 1
    for i in range(n-2):
        x = F[0][0]*M[0][0] + F[0][1]*M[1][0]
        y = F[0][0]*M[0][1] + F[0][1]*M[1][1]
        z = F[1][0]*M[0][0] + F[1][1]*M[1][0]
        w = f[1][0]*M[0][1] + F[1][1]*M[1][1]

        F[0][0] = x
        F[0][1] = y
        F[1][0] = z
        F[1][1] = w

    return result[0][0]

정복법에 의해 $O(\log{n})$ 의 수행 시간의 풀이로 최적화 할 수 있는데 방법은 매우 간단하다.

예를 들어, $2^8$ 를 풀어보자. $2^8$ 을 푸는 방법은 두가지가 있는데,

첫째는,
$2 \times 2 \times 2 \times 2 \times 2\times 2\times 2\times 2$
이렇게 2를 8번 곱하는 것이다.

두번째는, 지수의 특성을 이용하는 방법으로 $((2^2)^2)^2$ 제곱된 값을 제곱하는 것이다. 이런식으로 계산하면 8번 계산 했던걸 3번만 계산하면 된다. 그리고 3은 $\log_{2}8$ 값과 동일하다.

즉, 지수계산은 지수의 특성을 이용해서 $O(\log{n})$ 수행시간으로 풀수 있다.

def matrix_fibonacii(n):
    F = [[1, 1],[1, 0]]
    if n == 0:
        return 0
    else:
        power(n-1, F)
        return F[0][0]
    
def multi(F, b):

    x = (F[0][0] * b[0][0]) + (F[0][1] * b[1][0]) 
    y = (F[0][0] * b[0][1]) + (F[0][1] * b[1][1])
    z = (F[1][0] * b[0][0]) + (F[1][1] * b[1][0])
    w = (F[1][0] * b[0][1]) + (F[1][1] * b[1][1])

    F[0][0] = x
    F[0][1] = y
    F[1][0] = z
    F[1][1] = w

def power(n, F):
    
    if( n == 1 or n == 0):
        return
    else:
        power(n//2, F)
        multi(F,F)
        if (n % 2) != 0:
            M = [[1, 1],[1, 0]]
            multi(F,M)

에필로그

재귀적인 방법에서는 어떻게 반복적인 연산을 처리 했는지 확인하는 것이 중요했고,
동적 계획법에서는 어떻게 반복 연산을 제거하려고 했는지가 중요했다.
행렬과 분할 정복법을 적용은 문제를 바라보는 관점의 전환이 중요하지 않았을까?

개발자라면, 최적화 하기위해 고민하고 또 고민해야 한다.

'어떻게 하면 반복하는 것을 줄일 수 있을까?'에 대한 해답을 찾으려고 노력해야 한다. 한번에 완벽하게 끝나는 경우는 없더라. 수많은 테스트와 검증이 필요하더라.

기업들이 코딩 테스트를 하는 건, 능력 있는 개발자를 뽑기위한 방법일까? 능력 없는 개발자를 거르기 위한 방법일까?

참고 사이트

• 나무위키-피보나치 수열
• geeksforgeeks-Program for Fibonacci numbers
• star7sss-[분할정복/DQ]백준 11444 피보나치 수 6 - 파이썬
• falling_star3-[프로그래머스 Level2][Python] 행렬의 곱셈
• shoark7-피보나치 수열 알고리즘을 해결하는 5가지 방법
• jsSyntaxTree