피보나치 수열(프로그래머스)

피보나치 수열 풀러 가보기

프로그래머스

 

피보나치 수열이란 0,1,1,2,3,5,8... 이런식으로 n번째의 항이 n-2번째 수와 n-1번째 수의 합을 갖는 형식을 말한다.

 

가장 먼저 기초적인 반복문을 이용하여 해당 풀이를 진행하였다.

// 단순 반복문을 이용한 피보나치 수열 계산

public static int solution1(int n) {
    int f0 = 0;
    int f1 = 1;
    int f2 = 2;

    for (int i = 1; i < n; i++) {
        f2 = (f0 + f1) % 1234567;
        f0 = f1;
        f1 = f2;
    }
    System.out.println(f2);
    return f2;
}

변수 3개와 반복문 만을 이용하여 계산한 풀이법이다.

for반복문의 시작값이 i=1이기 때문에 총 n-1번이 진행되게 된다.

기본적으로 값이 정해져 있는 f(0), f(1)을 제외하고 f(2)부터 실질적으로 값이 계산되기 때문에 반복문을 이용하여 피보나치 수를 구하려 한다면 실제로 계산을 시행하는 횟수는 n-1번이 필요하기 때문이다.

 

두번째 풀이는 똑같이 반복문을 이용하였으나 추가적으로 ArrayList를 이용하였다.

// ArrayList를 이용한 피보나치 수열 계산

public static int solution2(int n) {

    ArrayList<Integer> arr = new ArrayList<>();
    arr.add(0);
    arr.add(1);

    for(int i = 1; i < n; i++){
        arr.add(arr.get(i)+arr.get(i-1));
    }

    System.out.println(arr.get(n));
    return arr.get(n);

}

해당 방법도 반복문의 시작을 1로 설정하여 n보다 작을때까지로 총 n-1번의 반복이 진행되도록 설정하였다.

그냥 배열을 사용하는 방법도 있지만 배열의 크기를 미리 정해놓고 하는 것보다 ArrayList는 동적으로 크기를 변환할 수 있기 때문에 n의 값을 이용하여 계속 늘리는 방식을 사용하는 것이 좋을 것 같다고 생각하였다. (유연성)

 

마지막으로 세번째 풀이는 재귀함수를 이용한 방법이다.

// 재귀 함수를 통한 피보나치 수열 계산
public static int solution3(int n) {

    if(n < 2){
        return n;
    }


    return solution3(n-1) + solution3(n-2);

}

이런식으로 n이 2이상의 값이 나올경우 재귀함수를 호출하여 f(0)=0의 값을 가지거나 f(1)=1의 값을 가질때까지 쪼개지도록 나눠서 계산하는 방식이다.

하지만 재귀함수의 시간 복잡도는 무려 O(2ⁿ)이다.

n이 커질수록 수행해야하는 연산의 크기가 기하급수적으로 커지기 때문에 권장하지 않는 방식이지만 이런 방식도 있다 라는 생각으로 풀어봤다. 

 

추가적으로 이런 재귀 함수를 조금 업그레이드 해준다면 충분히 사용이 가능하다는 글을 보았다. 

메모이제이션(Memoization)

메모이제이션은 이전에 계산한 결과값을 저장하고, 같은 값을 다시 계산할 필요가 없도록 하는 기법이다.

즉, 한번 계산한 결과값을 저장해두고 다음에 값을 요청하면 저장된 값을 사용한다는 점에서 재귀호출에 최적화 되어있다.

배열이나 해시맵을 이용하여 사용할 수 있다고 하는데 다음에 기회가 되면 한번 사용해보도록 해야겠다.

참고로 메모이제이션을 이용하여 재귀함수를 호출할 경우의 시간복잡도는 O(n)으로 기존의 재귀함수보다 매우 빠르다.