항해99 TIL 8일차 (피보나치 수 / 프로그래머스)

문제         

프로그래머스

 

 

 

1 번째 시도   

 

간단한 피보나치 문제입니다. 코딩을 처음 배울 때 피보나치 프로그램을 배워 어렵지 않게 재귀함수로 구현했습니다.

import java.util.*;

class Solution {
    
    public int solution(int n) {
        
        return (int)(fibonachi(n) % 1234567);
        
    }
    
    public long fibonachi(int n) {
        if( n == 0)
            return 0;
        else if(n == 1)
            return 1;
        else
            return fibonachi(n-1) + fibonachi(n-2); 
    }
}

 

문제를 너무 얕봤습니다. 시간 초과가 발생했습니다. 재귀함수 시간복잡도에 대해 알아봐야겠습니다. 

 

최악의 경우 시간 복잡도: O(2^n)

이는 각 단계마다 호출 수가 2배씩 증가하기 때문에, n이 1 증가할 때마다 필요한 계산량이 거의 2배씩 증가합니다.

 

시간 복잡도 개선 방법

피보나치 수열을 계산하는 데 있어서 재귀 호출을 사용하는 것은 간단하고 이해하기 쉽지만, 많은 중복 계산을 수행한다는 단점이 있습니다. 이를 해결하기 위해 동적 계획법(Dynamic Programming) 또는 메모이제이션(Memoization) 기법을 사용할 수 있습니다. 이러한 방법들은 이미 계산된 결과를 저장해 두었다가 재사용함으로써 중복 계산을 줄이고, 시간 복잡도를 O(n)으로 개선할 수 있습니다.

 

2 번째 시도  

 

다이나믹 프로그래밍 기법을 적용했습니다.

class Solution {

    public int solution(int n) {
        long[] fib = new long[n+1];
        fib[0] = 0;
        fib[1] = 1;
        for(int i = 2; i <= n; i++) {
            fib[i] = (fib[i-1] + fib[i-2]) % 1234567;
        }
        return (int)fib[n];
    }
}

 

 

오늘 다이나믹 프로그래밍 맛을 살짝 봤습니다. 다른 문제도 풀어보며 다이나믹 프로그래밍을 학습해야겠습니다.

(나중에 아래에 다이나믹 프로그래밍에 관한 링크를 걸어놓겠습니다.)