[Level2] 피보나치 수

기본기가 탄탄해야 한다는 것을 다시 한 번 느낀다. 

[문제 설명]

https://programmers.co.kr/learn/courses/30/lessons/12945

코딩테스트 연습 - 피보나치 수

 

[풀이 과정]

문제 풀이에 앞서 피보나치에 대해 간단히 기록하겠다. 

 

n의 피보나치 수는 n-1, n-2 피보나치 수를 포함하고 있다. 

이렇게 큰 해에 작은 해를 포함하고 있으면 최적 부분 구조(Optimal Substructure)를 가졌다고 말한다.

최적 부분 구조를 가진 문제는 재귀를 이용하여 해를 구할 수 있다. 하지만 때때로 재귀는 중복 계산으로 인해 엄청난 비효율을 초래할 수 있다. 예를 들어 fib(7)을 구하는데 fib(5)는 2번, fib(4)는 3번,  fib(3)은 5번 호출된다. 

때문에 피보나치를 재귀를 이용하면 지수 함수에 비례하는 시간이 든다. 즉, 주어진 매개변수 n이 커질수록 실행시간이 증가하게 되는 것이다.  (시간 복잡도 : O(2^n))

 

출처 : https://shoark7.github.io/programming/algorithm/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9D%84-%ED%95%B4%EA%B2%B0%ED%95%98%EB%8A%94-5%EA%B0%80%EC%A7%80-%EB%B0%A9%EB%B2%95 (사진 클릭하면 이동)

 

 

// 반복 계산을 없애는 방법

memoization과 DP를 이용하여 피보나치를 중복 계산 없이 구현할 수 있다.

1. memoization

만약 fib(3)을 처음 계산했을 때 어딘가에 저장해놓고 또 필요할 때 그대로 가져다 쓰면 두번 계산할 필요가 없을 것이다. 

이처럼 재귀는 사용하되 한 번 호출된 것은 메모해둠으로서 중복호출을 피하는 방법이 바로 메모이제이션이다. 

이것은 탑다운(Top-down) 방식의 동적프로그래밍으로 위에서 아래로 해를 구해나가는 하향식 방법이다. 

(시간복잡도 : 선형시간 O(n))

package com.algorithm.level2;

public class Test12 {
    public static void main(String[] args) {
        int[] memo = new int[11];
        memo[0] = 0;
        memo[1] = 1;
        for (int i = 0; i <= 10; i++) {
            System.out.print(memoization_fib(i, memo) + " ");
        }
    }

    public static int memoization_fib(int n, int[] memo) {
        if (n == 0) {
            return memo[0];
        }

        if (n == 1) {
            return memo[1];
        }

        if (memo[n] != 0) {
            return memo[n];
        }

        memo[n] = memoization_fib(n - 1, memo) + memoization_fib(n - 2, memo);
        return memo[n];
    }
}

// 0 1 1 2 3 5 8 13 21 34 55 

 

2. DP

동적프로그래밍은 인덱스를 이용해 배열에 작은 것부터 저장해가면서 저장하는 방식이다.

for문을 돌면서 앞에서 구해 높은 작은 두 배열값을 가져다가 더하면 된다.

이것은 아래에서 위로 해를 구해나가는 바텀업(Bottom-up) 동적프로그래밍으로 상향식 방법이다. 

(시간복잡도 : 선형시간 O(n))

package com.algorithm.level2;

public class Test12 {
    public static void main(String[] args) {

        int n = 7;
        int[] fib = new int[n+1];
        System.out.println(dp_fib(n,fib));
    }

    public static int dp_fib(int n, int[] fib) {
        fib[0] = 0;
        fib[1] = 1;
        for (int i=2; i <=n; i++) {
            fib[i] = fib[i-1] + fib[i-2];
        }

        return fib[n];
    }
}

 

 

// 모듈러 연산

문제 풀이로 다시 넘어온다. 

처음에 문제을 풀고 채점을 하니 테스트 케이스 7번쯤부터 전부 실패처리가 떴다. 

실패처리된 이유는 어떤 분의 답변을 읽고 알 수 있었다. (programmers.co.kr/questions/11991)

요약을 하자면, 

 

 int 자료형은 저장할 수 있는 숫자 범위가 -2147483648 ~ 2147483647 이다. 

이처럼 각각의 변수가 사용하는 자료형은 저장할 수 있는 숫자 범위가 존재하고 이를 벗어날 경우 예상치 못한 결과를 반환할 수 있다.

그런데 피보나치 수는 엄청나게 빠르게 증가한다. 44번째 피보나치수만 해도 2,971,215,073 으로 이미 int 자료형의 범위를 벗어나게 된다. 그렇게 때문에 1234567로 나누기도 전에 이미 피보나치 수를 구하는 과정에서 int 자료형 범위를 초과하여 실패처리가 난 것이다.

이때 아주 고마운 공식이 존재하는데 바로 모듈러 연산이다.

모듈러 연산에 의하면 (A + B) % C 는 ((A % C) + (B % C)) % C 와 결과가 같다.

당연하게도 1234567로 나눈 나머지 값은 항상 1234567보다 작을 것이다. 때문에 피보나치수를 구하여 저장하기전에 1234567로 나눈 나머지를 저장하면 int 자료형을 벗어나지 않고도 답을 구할 수 있다.

 

[JAVA 코드]

package com.algorithm.level2;

public class Test19 {
    public static void main(String[] args) {
        int n = 10000;
        System.out.println("answer : " + solution(n));
    }

    public static int solution(int n) {
        int  answer = 0;
        int [] memo = new int [n+1];
        memo[0] = 0;
        memo[1] = 1;

        int param = 1234567;

        answer = fib(n, param, memo) % param;
        return answer;
    }

    public static int  fib(int n, int param, int [] memo) {
        if (n==0) {
            return memo[0];
        }

        if (n==1) {
            return memo[1];
        }

        if (memo[n]!=0) {
            return memo[n];
        }

        memo[n] = ((fib(n-1, param, memo) % param) + (fib(n-2, param, memo) % param));
        return memo[n];
    }
}