피보나치 수(2레벨)

class Solution {
    fun solution(n: Int): Int {
        var answer = 0
        var array: Array<Int> = Array(n+1, {0})
        array[0] = 0
        array[1] = 1
        for(i in 2..n)
        {
            array[i] = ((array[i-2] % 1234567) + (array[i-1] %1234567) ) % 1234567
        }
        answer = array[n]
        return answer
    }
    
    //fibo 함수는 사용하지 않음
    fun fibo(n: Int): Int {
        
        if(n == 0)
            return 0
        else if(n == 1)
            return 1
        else
            return (fibo(n-1) % 1234567 + fibo(n-2) % 1234567) % 1234567
    }
    
    
}

이번 문제는 알고리즘 자체는 쉬웠으나 결론적으로는 알아야 하는 게 많아서 어려웠다.

 

아래 fibo 함수를 구현해 귀납식으로 해결하려고 했는데 7번 문제부터 안풀려서 이유를 찾아보았다. 

문제에 엉뚱하게 124567의 나머지를 구하라는게 그 이유에 핵심이였다.

피보나치 수열은 n 값이 커지면 나중에 숫자가 엄청 커지기 때문에 int 자료형으로는 데이터를 담을 수 없기에

1234567의 나머지를 통해 확실하게 int 자료형 범위 내로 받을 수 있는 것이다.

그리고 또한 모듈러 산술 특징을 보면

(a+b) mod c = (a mod c) + (b mod c) mod c

이와 같으므로 이를 활용해 구현할 수 있다.

 

하지만 되지않았다.

그래서 시간을 투자한 결과 귀납식 자체에 문제라는 것을 깨달았다.

fibo 함수를 보면 귀납식으로 구현했지만 이는 소스가 간결해서 사용하기 편하지만 치명적인 단점이 있다.

피보나치 알고리즘의 경우에는 숫자가 커지면 커질수록 비정상적으로 연산량이 많아진다.

그리고 쓸데없이 중복연산을 하는 것도 있다.

그래서 스택오버플로우가 발생해 계산이 안된것이다. 

 

그래서 피보나치 반복적 방법을 이용해 풀었다.

 

요약

문제1 피보나치 크기 커지면 int의 범위을 넘어서게됨 => 모듈러 산술 활용

문제2 귀납적 방법은 연산중복, 값이 커질수록 연산이 비정상적으로 증가해 오버플로우 현상 발생 => 반복적 방법 

 

해설

n+1만큼의 공간을 가진 정적 배열을 만든다.
0 과 1의 값을 초기값으로 각각 넣어준다.
그리고 반복문을 통해
2부터 n까지 
f(n) = f(n-2) + f(n-1) 을 반복해준다.
그러면 배열에 f(2)부터 f(n)까지 차곡차곡 값이 들어가지며 이렇게 할 시 중복 연산을 피할 수 있다.
또한 잊지않고 나머지연산을 활용해주면 문제없이 answer를 얻을 수 있다.