피보나치 수열

이란?

👉 0(0항)과 1(1항)로 시작하고 이전의 두 수 합을 다음 항으로 하는 수열

피보나치 수열 함수

피보나치 수열의 i번 째 값을 계산하는 함수 F
👉 F0 = 0, F1 = 1
👉 Fi = Fi-1 + Fi-2 (단, i >= 2 일 때)

피보나치 수를 구하는 재귀함수

위의 정의를 이용하여 피보나치 수열의 i번째 항을 반환하는 함수를 재귀함수로 구현 가능

fibo(n)
    IF n < 2 : RETURN n
    ELSE      : RETURN fibo(n-1) + fibo(n - 2)

이 때 fibo(n)는 n항을 구하는 메소드(함수)

피보나치 수열을 구했을 때 문제점

피보나치를 재귀로 구현하였을 때 문제점은 매우 많은 중복 호출이 존재한다는 점

그렇다면 중복을 피할 수 있는 방법은 없을까?
이는 아래의 메모이제이션을 활용하면 중복을 줄일 수 있음

메모이제이션(memoization)

👉 컴퓨터 프로그램을 실행할 때 전에 계산했던 값을 메모리에 저장하여 매번 다시 새롭게 계산하지 않도록 함으로써 중복을 최소화하고 전체 실행속도를 빠르게 하는 알고리즘 기법
👉 피보나치 수를 구하는 알고리즘에서 메모이제이션을 사용하면 실행시간을 O(n)으로 줄일 수 있음

메모이제이션 Pseudo code

memo하기 위한 배열 선언 및 0으로 초기화
memo[0] = 0
memo[1] = 1

fibo(n)
    IF n >= 2 AND memo[n] = 0
            memo[n] <- fibo(n-1) + fibo(n-2)
    RETURN memo[n]

👉 배열 memo의 index : input값이나 판단조건을 의미
👉 배열 memo의 value : 계산된 값
👉 배열 memo의 초깃값은 계산 결과로 절대 나올 수 없는 값으로 설정해야 계산의 유무를 판단할 수 있음

메모이제이션을 구현하기 위해...

👉 추가적인 메모리 공간이 필요
👉 재귀 함수 호출로 인해 시스템 호출 스택을 사용
👉 실행 속도 저하 또는 오버플로우가 발생할 수 있음
내일은 관련 알고리즘인 DP에 대해 정리해보아야겠다.