[cote] 피보나치 수

위키피디아

 

[프로그래머스] level 2 - 피보나치 수

프로그래머스

 

문제 설명

 

문제 설명
피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다.

예를들어

F(2) = F(0) + F(1) = 0 + 1 = 1
F(3) = F(1) + F(2) = 1 + 1 = 2
F(4) = F(2) + F(3) = 1 + 2 = 3
F(5) = F(3) + F(4) = 2 + 3 = 5
와 같이 이어집니다.

2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.

 

제한사항

n은 2 이상 100,000 이하인 자연수입니다.

 

 

1차 풀이 - 단순 회귀 방식

낮은 숫자에 한해서는 가능하지만 n=50인 경우만 가도 눈에 띄게 느려짐.

n = 50 일 경우 25초 정도 소요됨.

    public long getFibonacciNum(int n) {
        if (n <= 0) {
            return 0L;
        } else if (n == 1 || n == 2) {
            return 1L;
        }
        return getFibonacciNum(n - 2) + getFibonacciNum(n - 1);
    }

 

2차 풀이 - 캐싱 방식

재귀 함수이므로 트리형식으로 뻗어나가기 때문에 같은 계산의 중복이 많아서(대략 2^n개까지 등장)라고 생각했다.

 

Fn = Fn-2 + Fn-1 이므로 Fn-2을 계산하는 동안 캐시 Array가 채워져 있으면 다음 계산이 빨라진다고 생각했고 다음과 같이 코드를 작성했다.

    public long getFibonacciNumWithCache(int n) {
        if (cache == null) {
            cache = new long[n+1];
            cache[0] = 0L;
            cache[1] = 1L;
            cache[2] = 1L;
        }
        if (n <= 0) {
            return cache[0];
        } else if (n == 1) {
            return cache[1];
        }
        cache[n] = cache[n - 2] + cache[n - 1];
        if (cache[n] != 0) {
            return cache[n];
        }
        return getFibonacciNumWithCache(n - 2) + getFibonacciNumWithCache(n - 1);
    }

위에서 했던 방식으로 n = 50 일 때도 빠르게 작동했다.

하지만 n이 3만 중반대를 넘어가면서 StackOverflow가 떴다.

n = 37000일 때 에러

3차 풀이 - 비네의 식을 이용한 풀이

 구하는 방식이 너무 느린것인가 싶어 다음 포스팅을 찾아 그대로 풀어보았다.

 

피보나치 수열 7.7배 빠르게...

[Python] 피보나치 수열 7.7배 빠르게 계산하는 방법

 

 

    public double getFibonacciNumByFormula(int n) {
        double sqrt5 = Math.sqrt(5);
        return (1d/sqrt5) * (Math.pow((1d+sqrt5)/2d, n) - Math.pow((1d-sqrt5)/2d, n));
    }

하지만, 이것이 문제가 아니었다. 피보나치 수가 너무 커지는 나머지 담을 수가 없었던 것이 이유였다.

n = 37000일 때 피보나치 수

어떤 다른 방식의 아이디어가 있는지 프로그래머스 팁 게시판에서 찾아보았다.

4차 풀이 - 비네의 식을 이용한 풀이

 나머지 값 또한 모듈러 연산의 성질에 따라 쪼갤 수 있다는 것이 키포인트 였고, 1234567로 나누는 것은 int안에 머물게 함을 의미하는 것이었다.

    public long getFibonacciNumNoRecursion(int n) {
        if (cache == null) {
            cache = new long[n + 1];
            cache[0] = 0L;
            cache[1] = 1L;
        }
        for (int i = 0; i <= n; i++) {
            if (i >= 2) {
                long sum = cache[i - 2] + cache[i - 1];
                cache[i] = sum % 1234567L;
            }
        }
        return cache[n];
    }

 

 이번에는 회귀를 사용하지 않았고, 위의 설명에 따라 매번 계산 단계에서 나누기를 해주니 정답 처리가 되었다.

 

느낀 점

 오래걸려 헤메었지만 속도 및 알고리즘의 종류만이 중요한 것이 아님을 깨달았다. 자료형과 예상되는 값의 크기를 간과하였고 문제를 풀음에 있어 1,2,3차까지 헤메게 만들었다. 37000번째의 피보나치 수가 long에 담길 것이라고 당연하게 생각하여 문제를 키운 것 같았다.( long이면 충분히 큰 타입이라고 생각했다.)

 

 추가로 모듈러 연산에 대한 지식도 알게 되어 추 후 이런 문제가 나올 경우 도움이 많이 될 듯 싶다.