[CS] [알고리즘] 피보나치 수열 구현방식 3가지

• 피보나치 수열 구현 방식 세 가지를 말해보시고, 시간복잡도와 공간복잡도를 설명해 주세요.

피보나치 수열은  재귀 함수 , 동적 프로그래밍, 반복문을 이용해서 구현할 수 있습니다.

재귀함수는 호출 시 두개의 분기가 계속해서 생기기 때문에 시간복잡도가 O(2^n)로 매우 비효율적입니다.

동적프로그래밍 방식은 이전에 구해놓은 값을 재사용하기 때문에 n까지 한번씩만 계산하여 시간 복잡도가 O(n)이 됩니다.

반복문은 for문을 한 번만 돌기 때문에 마찬가지로 시간복잡도가 O(n)이 됩니다.

 

시간복잡도와 공간복잡도는 알고리즘 효율성을 평가하는 척도로,

시간 복잡도는 얼마나 빠르게 실행되는지, 공간 복잡도는 얼마나 많은 저장 공간이 필요로 하는지를 나타냅니다.

피보나치 수열 구현 시 재귀함수와 동적프로그래밍을 사용하면 공간복잡도가 O(N), 반복문을 사용하면 O(1)이 됩니다

 

출처: https://velog.io/@im_lily/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98-%EC%88%98%EC%97%B4-%EC%8B%9C%EA%B0%84%EB%B3%B5%EC%9E%A1%EB%8F%84

 

시간복잡도 &공간복잡도

• 알고리즘 계산 복잡도는 다음 두 가지 척도로 표현될 수 있음
  • 시간 복잡도: 얼마나 빠르게 실행되는지
  • 공간 복잡도: 얼마나 많은 저장 공간이 필요한지
• 알고리즘은 시간 복잡도가 중심
  • 시간과 공간은 반비례적 경향이 있기 때문에 통상 둘 다를 만족시키기는 어려움
  • 공간 복잡도보다는 시간 복잡도가 우선

 

피보나치 수열: 첫째, 둘째항은 1이고 그 다음 항부터는 이전 항 2개를 더한 값으로 이루어진 수열

• 시간복잡도
  • 재귀 함수 : O(2^n)
  • 동적 프로그래밍: O(n)
  • 반복문 : O(n)

 

 재귀함수

• 시간 복잡도: O(2^N)
  • 호출 시 두개의 분기가 계속해서 생기기 때문
• 공간 복잡도: O(N)
  • 재귀함수를 사용하였으므로, n에 따라 변수 n이 n개가 만들어지게 됨

• 자기 자신을 다시 호출하여 작업을 수행하는 방식
• 재귀로 두개의 분기가 계속해서 생기기 때문에 시간복잡도가 O(2^n)로 매우 비효율적
  •  (알고리즘 문제를 풀 때 재귀함수로 풀면 대부분 효율성 테스트는 통과하지 못함)

def fibo(n):
    if n in (1,2):
        return 1
    return fibo(n-1) + fibo(n-2)

 

동적 프로그래밍(Dynamic Programming(DP))

• 시간 복잡도: O(N)
  • 이전에 구해놓은 값을 재사용하기 때문에 n까지 한번씩만 계산
• 공간 복잡도: O(N)
  • 재귀함수를 사용하였으므로, n에 따라 변수 n이 n개가 만들어지게 됨
• 하위 문제 결과 저장 후 상위 문제 해결할 때 재사용하는 방식(상향식 문제 풀이)
• 재귀함수를 사용했을 때 중복되는 계산과정을 재사용할 수 있다. 
• n까지 한번씩만 계산해주면 문제를 해결할 수 있음→ 시간 복잡도가 O(n)

def fibonacci(n):
    val=[0,1]
    if n>=2:
        for i in range(2,n+1):
            val.append(val[i-1]+ val[i-2])
    return val[n]

 

반복문

• 시간 복잡도: O(N)
• 공간 복잡도: O(1)
  • n의 값에 상관없이 변수 n, 변수 fac, 변수 index 만 필요

def fibo(n):
    if n < 2:
        return n

    a, b = 0, 1
    for i in range(n-1):
        a, b = b, a + b

    return b

 

 

---

 

자바 코드 참고 링크

• 재귀함수

public static int fibo(int x) {
        if (x <= 1) {
            return x;
        } else {
            return fibo(x - 1) + fibo(x - 2);
        }
    }

• 동적 프로그래밍

private static int getDpFibo(int fiboCnt) {
   fiboDpArray = new int[fiboCnt + 1];
        
   fiboDpArray[0] = 0;
   fiboDpArray[1] = 1;
        
   if (fiboCnt > 1) {
     for (int i = 2; i <= fiboCnt; i++) {
        fiboDpArray[i] = fiboDpArray[i - 2] + fiboDpArray[i - 1];
     }
   }
        
    return fiboDpArray[fiboCnt];

• 반복문

private static int getLoopFibo(int fiboCnt) {
    if (fiboCnt <= 1) {
        return 1;
    } else {
        int a = 0;
        int b = 1;
        int sum = 0;
        
        for (int i = 2; i <= fiboCnt; i++) {
            sum = a + b;
            a = b;
            b = sum;
        }
            
        return sum;
    }
}

 

---

Swift 코드 참고 링크

• 재귀함수

func fibonacci(_ n: Int) -> Int {
		if n <= 1 { return n }
    return fibonacci(n - 1) + fibonacci(n - 2)
}

• 동적 프로그래밍

func fibo(_ n: Int) -> Int {
    var cache: [Int] = [0, 1]
    
    guard n > 1 else { return n }
    
    for num in 2...n {
        cache.append(cache[num - 2] + cache[num - 1])
    }
    
    return cache[n]
}

• 반복문
  • 출처: https://hongssup.tistory.com/322 [Outgoing Introvert:티스토리]

func Fibonacci(_ n: Int) -> Int {
    var s1 = 0, s2 = 1
    for _ in 0..<n {
        let tmp = s1
        s1 = s2
        s2 = tmp + s2
    }
    return s1
}