[알고리즘] 피보나치 수열을 구현하는 여러가지 방법

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 ...

위 수열처럼 n번째 항의 수가 n-1 + n-2로 구성되는 수열을 피보나치 수열이라 한다. (단, n은 n<2)

피보나치 수열을 구현하는 방법으로는 몇가지가 있지만 그 중 재귀함수를 사용하는 방법이 있다.

 

int fibo(int n) {
	if (n <= 2) return n;
    return fibo(n - 1) + fibo(n - 2);
}

다만 위 방법은 동그라미친 부분이 중복 계산된다.

따라서 불필요한 계산을 반복하기 때문에 n의 값이 커질수록 비효율적인 문제가 있다.

int dp[] = {0, 1};

int solution(int n) {
    if(n == 0) return 0;
    else if (!dp[n]) 
        dp[n] = solution(n - 1) + solution(n - 2);
    return dp[n];
}

이 방법은 위 개념을 적용한 코드로, 0, 1을 미리 저장해둔 dp라는 이름의 배열에 값을 계산하여 저장하는 방식이다. 

n번째 배열에는 n번째 값이 저장된다.

dp[n]이 0일때는 아직 계산되지 않은 상태이기 때문에 계산하는 과정 없이 dp[n]을 반환하여 시간을 단축시킨다.

dp[0]은 0이라는 값을 계산하여 넣은 것이지만 조건문에 만족해 0보다 작은 자리값을 계산하여 오류가 날 수 있기 때문에 n == 0일때의 조건을 추가해준다.

int dp[] = {0, 1};

int solution2(int n) {
    if(dp[n]) return dp[n];
    
    for(int now = 2; now <= n; now++) {
        dp[now] = dp[now - 1] + dp[now - 2];
    }
    return dp[n];
}

또다른 방법으로는 반복문을 사용하는 방법이다.

조건문을 통해 dp[n]을 계산했는지 확인한 후 계산한 경우 dp[n]의 값을 반환한다.

그게 아니라면 for문을 통해 n의 자리까지 계산하여 배열에 저장한다.

위 방법에서는 dp[n]의 값을 계산하지 않은 경우를 조건문의 조건에 넣어주었지만,

아래방법에서 이렇게 적용할 경우 불필요하게 코드의 줄이 길어지기 때문에 위와같이 변경하여 적어주었다.