2. 피보나치 수

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

 

저의 블로그에서도 다룬 적 있는 문제입니다. 

https://comdoc.tistory.com/entry/33-피보나치-수열과-동적-프로그래밍

 

파이썬

재귀의 예로 많이 사용됩니다만, 문제의 조건인 100,000은 파이썬의 재귀 한계를 넘겨 버립니다. 

RecursionError: maximum recursion depth exceeded in comparison

재귀를 쓰지 말고, 반복문을 사용합니다. 

 

문제를 그대로 코딩하면 이렇습니다만.. 

def solution(n):
    f0, f1 = 0, 1
    for i in range(2, n+1):
        f0, f1 = f1, (f1 + f0)
    return f1 % 1234567
    
"""
테스트 1 〉	통과 (0.05ms, 10.7MB)
테스트 2 〉	통과 (0.04ms, 10.7MB)
테스트 3 〉	통과 (0.04ms, 10.8MB)
테스트 4 〉	통과 (0.04ms, 10.7MB)
테스트 5 〉	통과 (0.04ms, 10.7MB)
테스트 6 〉	통과 (0.04ms, 10.7MB)
테스트 7 〉	통과 (0.14ms, 10.7MB)
테스트 8 〉	통과 (0.08ms, 10.7MB)
테스트 9 〉	통과 (0.05ms, 10.7MB)
테스트 10 〉	통과 (0.15ms, 10.8MB)
테스트 11 〉	통과 (0.06ms, 10.6MB)
테스트 12 〉	통과 (0.07ms, 10.8MB)
테스트 13 〉	통과 (111.05ms, 10.8MB)
테스트 14 〉	통과 (106.98ms, 10.8MB)
"""

이렇게 해주는 게 더 좋을 것 같습니다. 

큰 수에서 더 빠릅니다. 

def solution(n):
    f0, f1 = 0, 1
    for i in range(2, n+1):
        f0, f1 = f1, (f1 + f0) % 1234567
    return f1
    
"""
테스트 1 〉	통과 (0.04ms, 10.7MB)
테스트 2 〉	통과 (0.04ms, 10.7MB)
테스트 3 〉	통과 (0.04ms, 10.6MB)
테스트 4 〉	통과 (0.04ms, 10.7MB)
테스트 5 〉	통과 (0.05ms, 10.6MB)
테스트 6 〉	통과 (0.05ms, 10.7MB)
테스트 7 〉	통과 (0.13ms, 10.8MB)
테스트 8 〉	통과 (0.09ms, 10.7MB)
테스트 9 〉	통과 (0.06ms, 10.6MB)
테스트 10 〉	통과 (0.14ms, 10.6MB)
테스트 11 〉	통과 (0.07ms, 10.7MB)
테스트 12 〉	통과 (0.08ms, 10.7MB)
테스트 13 〉	통과 (6.72ms, 10.7MB)
테스트 14 〉	통과 (6.68ms, 10.7MB)
"""

 

자바스크립트

function solution(n) {
    let f0 = 0, f1 = 1
    for (let i = 2; i < n + 1; i++) {
        [f0, f1] = [f1, (f0 + f1) % 1234567]
    }
    return f1
}

 

자바

class Solution {
    public int solution(int n) {
        int fib0 = 0, fib1 = 1, answer = 0;
        for (int i = 2; i <= n; i++) {
            answer = (fib1 + fib0) % 1234567;
            fib0 = fib1;
            fib1 = answer;
        }
        return answer;
    }
}

 

코틀린

코틀린은 한 줄에 여러 변수를 선언할 수가 없습니다. 
배열을 사용해서 13줄을 11줄로 줄였습니다.

class Solution {
    fun solution(n: Int): Int {
        var fib = arrayOf(0, 1, 1)
        for (i in 2..n) {
            fib[2] = (fib[1] + fib[0]) % 1234567
            fib[0] = fib[1]
            fib[1] = fib[2]
        }
        return fib[1]
    }
}

 

고

func solution(n int) int {
	var fib0, fib1 int = 0, 1
    for i := 2; i <= n; i++ {
        fib0, fib1 = fib1, (fib0 + fib1) % 1234567
    }
    return fib1
}

 

C#

public class Solution
{
    public int solution(int n)
    {
        int[] answer = { 0, 1, 1 };
        for (int i = 2; i <= n; i++)
        {
            answer[2] = (answer[1] + answer[0]) % 1234567;
            answer[0] = answer[1];
            answer[1] = answer[2];
        }
        return answer[2];
    }
}