[프로그래머스](level 2)피보나치의 수

피보나치의 수

Before we go further

프로그래머스 1레벨을 어느정도 풀고 레벨 2를 풀기위해 몇 문제들을 보았습니다. 이때부터 저의 좌절이 시작된 듯 합니다ㅎㅎ 너무 어렵더군요... 그래서 주변에 의견을 물어보니 어느정도 알고리즘에 대한 지식이 없다면 풀기 어렵다고 하더군요.

그래서 제대로 알고리즘을 공부하면서 풀고자 프로그래머스 레벨 2 문제 피보나치의 수에 대해 작성하도록 하겠습니다.

피보나치의 수

역사와 같은 것들은 따로 작성하지 않겠습니다. 아래의 Refernce의 위키 링크를 타고 가시면 자세히 알 수 있습니다. 또한 깊이 있게 정리하는 것 역시 넘어가도록 하겠습니다. 현재 이해할 수 있고 사용하는 수준 정도로만 정리하고 넘어가도록 하겠습니다. 왜냐하면 깊이 있게 들어가는 순간 너무 어렵기 때문입니다.

정의

피보나치 수란

F0 = 0, F1 = 1로 정해 놓고

F1 = F2 = 1 이 되는 ( F2 = F0 + F1 = 1)

Fn = Fn-1 + Fn-2의 값을 가진다 정의입니다.

즉 0, 1, 1, 2, 3, 5, 8...로 증가된다는 뜻이죠.

여기서 중요한 점은

1. f0 = 0, f1 = 1로 둔다는 것
2. Fn = Fn-1 + Fn-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 이하인 자연수입니다.

입출력 예

n	return
3	2
5	5

입출력 예 설명

피보나치수는 0번째부터 0, 1, 1, 2, 3, 5, ... 와 같이 이어집니다.

풀이

• 유의할 점

  위에서 언급한 두가지

  1. f0 = 0, f1 = 1로 둔다는 것
  2. Fn = Fn-1 + Fn-2 로 값이 정의된다는 것입니다.

• 그리고 int 의 범위 입니다.

  int는 -2,147,483,648 ~ 2,147,483,647까지의 숫자밖에 인식이 되지 않습니다.

  따라서 해당 문제를 풀 시 (A+B) % C의 값이 ( (A % C) + (B % C) ) % C 와 같다는 성질을 이용해야합니다.

Code

저는 보통 아래와 같이 코드를 작성합니다.

package programmer_lv2;

public class FibonacciCal {
    public static void main(String[] args) {
         int n = 3;
        FibonacciCal fibonacciCal = new FibonacciCal();
        System.out.println(fibonacciCal.solution(n));
    }
    public int solution(int n) {
        int[] arr = new int[n+1];
        arr[0] = 0;
        arr[1] = 1;
        for(int i = 2; i <= n; i ++){
            arr[i] = arr[i-1] + arr[i-2];
        }
        return arr[n] % 1234567;
    }
}

우선 위의 코드는 결과적으로 실패하는 코드입니다.

그 이유는 위에 설명드린 바와 같이 int 타입의 범위 때문입니다.(참고로 java 의 long 타입의 범위 는 -9223372036854775808 ~ 9223372036854775807이지만 이 역시 벗어납니다ㅎㅎ)

피보나치의 수 의 경우 44번째 숫자만 되어도 int의 범위를 벗어나기 때문에 제대로된 값이 들어가지 않습니다.(음수의 값이 return된다던지, 정확한 값이 return 되지 않습니다.)

그래서 (A+B) % C == ( (A % C) + (B % C) ) % C를 이용해야 합니다.

Result

package programmer_lv2;

public class FibonacciCal {
    public static void main(String[] args) {
         int n = 3;
        FibonacciCal fibonacciCal = new FibonacciCal();
        System.out.println(fibonacciCal.solution(n));
    }
    public int solution(int n) {
        int[] arr = new int[n+1];
        arr[0] = 0;
        arr[1] = 1;
        for(int i = 2; i <= n; i ++){
            arr[i] = (arr[i-1] + arr[i-2]) % 1234567;
        }
        return arr[n];
    }
}

위의 코드와 같이 각각의 인덱스 값을 1234567로 나눈 나머지의 값으로 채워주게 되면 int의 범위 내에서 항상 해결됩니다!

앞으로도 꾸준히 알고리즘을 공부해야 할 듯 합니다. 고생하셨습니다.

Reference

https://ko.wikipedia.org/wiki/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98_%EC%88%98