03/26 알고리즘 공부(78) - 피보나치 수

조건

피보나치 수는 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 이하인 자연수입니다.

입출력 예

n	return
3	2
5	5

알고리즘 예상

1. 피보나치 수를 저장하는 fibonacci배열을 만든다.( 초기값 0, 1 )
2. i in 2..n 만큼 반복하는 반복문을 이용해  fibonacci[i-2] + fibonacci[i-1]값을 fibonacci[i]에 저장한다.
3. fibonacci[n] % 1234567을 리턴한다.

 

초기 코드

class Solution {
    fun solution(n: Int): Int {
        var answer = 0
        return answer
    }
}

 

내 코드

//실패
class Solution {
    fun solution(n: Int): Int {
        val fibonacci = mutableListOf(0, 1)
        for (i in 2..n){
            fibonacci.add(fibonacci[i-2]+fibonacci[i-1])
        }
        return fibonacci[n]%1234567
    }
}

10만번째 피보나치 수까지 계산해야하기 때문에 Int범위를 초과하는 것 같다.찾아보니 1000번째만 넘어도 Int범위를 초과한다. 아마 Long범위도 초과할 것 같은데 우선 Long으로 바꿔서 시도해보겠다.

// 실패
class Solution {
    fun solution(n: Int): Int {
        val fibonacci = mutableListOf<Long>(0, 1)
        for (i in 2..n){
            fibonacci.add(fibonacci[i-2]+fibonacci[i-1])
        }
        return (fibonacci[n]%1234567).toInt()
    }
}

똑같이 Long범위도 초과하여 실패하는 것으로 예상된다. 아예 list에 값을 추가할 때부터 나머지 계산을 진행하면 될 것 같다. 이러면 정수범위를 초과하는 일이 없으니 Long을 사용할 필요가 없을 것이고 마지막 리턴값에도 나머지를 구할 필요가 없을 것이다.

class Solution {
    fun solution(n: Int): Int {
        val fibonacci = mutableListOf<Int>(0, 1)
        for (i in 2..n) {
            //val next = (fibonacci[i - 2] + fibonacci[i - 1]) % 1234567
            //fibonacci.add(next)
            fibonacci.add((fibonacci[i - 2] + fibonacci[i - 1]) % 1234567)
        }
        return fibonacci[n]
    }
}

성공했다. 몇 번 건드려보니 next 변수를 지정하는 것 보다 해당 값을 add에 바로 넣는 것이 빨라 그렇게 바꿨다.

다른 사람의 풀이

class Solution {
    fun solution(n: Int): Int {
        var ans = Array(n+1) { i -> 0 }
        ans[1] = 1
        for(i in 2..n) ans[i] = (ans[i-1] + ans[i-2])%1234567
        return ans[n]
    }
}

 

개선점 또는 배운점

1. 길이가 n+1인 배열을 미리 선언해 내부의 값만 바꿔주는 방법을 이용했다. 내 방법보다 훨씬빠르다.
2. 몇가지 방법을 시도해보니 Array가 mutableList보다 빨랐다. Array는 크기가 고정인 대신 인덱스의 값을 바로 불러올 수 있고 mutableList는 해당 인덱스까지 순회하며 확인하기 때문에 인덱스가n인 원소에 접근하기 위해서 n번의 행동을 해야한다고 한다.
   따라서 컬렉션의 크기가 변하지 않고 내부 값만을 바꿀때는 Array를, 빈번하게 컬렉션의 크기가 바뀐다면 mutableList를 사용하는 것이 유리하다고 할 수 있다.

 

개선된 코드

class Solution {
    fun solution(n: Int): Int {
        val fibonacci = Array<Int>(n+1){0}
        fibonacci[1] = 1
        for (i in 2..n) {
            fibonacci[i] = (fibonacci[i - 2] + fibonacci[i - 1]) % 1234567
        }
        return fibonacci[n]
    }
}