프로그래머스 | Level 2 | 피보나치 수

Programmers | Level 2 | 피보나치 수

Problems

• 📘 Src: Programmers
• 🗂️ Cat: Dynamic Programming

Description

피보나치 수는 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을 완성해 주세요.

Constraints

• n은 2 이상 100,000 이하인 자연수입니다.

Examples

n	result
3	2
5	5

Solutions

• ⏳ TC: O(n)
• 💾 SC: O(n)

import java.util.*;

class Solution {
    
    public int solution(int n) {
        // 피보나치 수를 저장할 배열을 초기화
        int[] fibonacci = new int[n + 1];
        // 초기 값 설정
        fibonacci[0] = 0;
        fibonacci[1] = 1;
        int MOD = 1234567; // 나머지 연산을 위한 상수
        
        // 동적 프로그래밍을 이용하여 피보나치 수 계산
        for (int i = 2; i < fibonacci.length; i++) {
            // 현재 피보나치 수는 이전 두 피보나치 수의 합을 MOD로 나눈 나머지
            fibonacci[i] = (fibonacci[i - 1] + fibonacci[i - 2]) % MOD;
        }
     
        // n번째 피보나치 수 반환
        return fibonacci[n];
    }
}

Approaches

이 문제는 주어진 정수 n에 대해 n번째 피보나치 수를 1234567로 나눈 나머지를 구하는 문제입니다. 피보나치 수열은 동적 프로그래밍(DP)을 이용하여 효율적으로 계산할 수 있습니다.

피보나치 수열의 특성상, 이전 두 수를 더하여 다음 수를 구할 수 있습니다. 이를 위해 배열을 사용하여 중간 계산 결과를 저장함으로써, 계산 시간을 줄이고 중복 계산을 피할 수 있습니다. 문제의 조건에 따라 결과를 1234567로 나눈 나머지를 반환하여 결과가 너무 커지는 것을 방지합니다.

다음은 문제를 해결하는 과정입니다:

• 초기 조건 설정: F(0) = 0 및 F(1) = 1을 배열에 설정합니다.
• 동적 프로그래밍:
  • 배열을 사용하여 F(2)부터 F(n)까지의 값을 차례로 계산합니다.
  • 각 계산 결과를 1234567로 나눈 나머지를 배열에 저장합니다.
• 최종 결과 반환: 배열에서 F(n) 값을 반환합니다.

이 알고리즘의 시간 복잡도는 O(n)이며, 공간 복잡도는 중간 계산 결과를 저장하는 배열의 크기에 따라 O(n)입니다.