[프로그래머스 Lv. 2] 피보나치 수 - JAVA

문제

피보나치 수는 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, ... 와 같이 이어집니다.

 

---

문제 풀이

분석

피보나치 수열을 재귀로 구현하면 효율성이 떨어지므로 반복문 이용

메모이제이션 방법을 활용하면 재귀의 단점을 보완하면서 간결하게 코드 작성 가능

class FibonacciDP {
    public static int fibonacci(int n, int[] memo) {
        if (n <= 1) {
            return n;
        }
        if (memo[n] == 0) { // 아직 계산하지 않은 값이라면
            memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
        }
        return memo[n];
    }

    public static void main(String[] args) {
        int n = 10; // 예시로 10번째 피보나치 수를 구함
        int[] memo = new int[n + 1]; // 메모이제이션을 위한 배열

        for (int i = 0; i < n; i++) {
            System.out.print(fibonacci(i, memo) + " ");
        }
    }
}

 

 

내 소스 코드

class Solution {
    public int solution(int n) {
        // 피보나치 수열의 첫 두 값
        int a = 0;
        int b = 1;
        int result = 0;

        // 피보나치 수열의 값을 반복문으로 계산
        for (int i = 2; i <= n; i++) {
            result = (a + b) % 1234567;
            a = b;
            b = result;
        }

        // 결과 반환
        return result;
    }
}

 

추가로 공부할 부분

% 1234567로 나누는 것은 모듈러 연산

- 큰 숫자를 다루는 문제에서 계산 결과가 너무 커지는 것을 방지하기 위해 사용

모듈러 연산은 덧셈과 곱셈에 대해 다음과 같은 속성이 있음
(a + b) % c = ((a % c) + (b % c)) % c
(a * b) % c = ((a % c) * (b % c)) % c

 F(n) % 1234567는 F(n)의 결과를 1234567로 나눈 나머지를 반환

이렇게 하면 어떤 피보나치 수라도 0 이상 1234566 이하의 숫자로 변환

 

---

Lv.2  / Java / 연습문제

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges