[코딩테스트] - 피보나치 수 LV2 ( 프로그래머스(programmers) / java )👍

안녕하세요 나홀로전세집입니다.

개찐따 플랑크톤

오늘은 레벨2 피보나치 수 풀어보겠습니다.

 

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

프로그래머스

 

다음은 문제 설명입니다.

 

문제는 알고리즘 공부하면 자주 접하게 되는 피보나치 수 구하기 문제입니다.

보통 재귀함수를 배우기 위해 피보나치 수를 많이 사용합니다.

하지만 재귀함수는 코테에서는 효율적이지 않습니다.

재귀함수는 중복된 계산을 많이 하기 때문에 DP를 사용하여 푸는 것이 일반적입니다.

 

다음은 DP를 사용한 피보나치 문제 풀이 코드입니다.

class Solution {
    public int solution(int n) {
        if (n <= 1) { // 피보나치를 못하면 n 리턴
            return n;
        }
        int[] fib = new int[n + 1]; // 피보나치 값을 저장 할 배열
        fib[0] = 0; // 알고리즘에서 피보나치를 구하기 위한 최소 조건
        fib[1] = 1; // 알고리즘에서 피보나치를 구하기 위한 최소 조건
        
        for (int i = 2; i <= n; i++) { // 반복문으로 피보나치 구현
            fib[i] = (fib[i - 1] + fib[i - 2]) % 1234567;
        }
        return fib[n];
    }
}

 

피보나치 수는 코딩하면서 100번은 구해본 것 같습니다 ㅋㅋ

 

재귀함수로 다음 문제를 풀게되면 시간 초과가 날 것입니다. 

그래도 재귀함수로 피보나치 수를 구하는 것을 궁금해 할 수도 있기 때문에 코드를 올려드리겠습니다.

class Solution {
    public int solution(int n) { 
        return fib(n) % 1234567; // 피보나치 수 리턴
    }

    public int fib(int x) { // 피보나치 구하는 함수
        if (x == 0) { // x가 0일 때 함수 리턴
            return 0;
        } else if (x == 1) { // x가 1일 때도 함수 리턴
            return 1;
        }
        // 피보나치 수를 구하는 fib 함수를 함수 내부에서 또 사용하여 재귀함수 호출
        return fib(x - 1) + fib(x - 2);
    }
}

 

재귀함수를 사용하여 피보나치 수를 구하면 다음과 같습니다. 재귀함수는 함수 내부에서 자기 자신 함수를 다시 한번 호출하는 것을 말합니다. 보통 DFS 구현할 때 사용했던 것 같습니다.

 

오늘도 즐코딩 하시고 좋은 하루 되세요~

 

전체코드

class Solution {
    public int solution(int n) {
        if (n <= 1) { // 피보나치를 못하면 n 리턴
            return n;
        }
        int[] fib = new int[n + 1]; // 피보나치 값을 저장 할 배열
        fib[0] = 0; // 알고리즘에서 피보나치를 구하기 위한 최소 조건
        fib[1] = 1; // 알고리즘에서 피보나치를 구하기 위한 최소 조건
        
        for (int i = 2; i <= n; i++) { // 반복문으로 피보나치 구현
            fib[i] = (fib[i - 1] + fib[i - 2]) % 1234567;
        }
        return fib[n];
    }
}