💡 목적 : 복잡한 문제를 작은 하위문제로 나누어서 해결하는 DP알고리즘. 난이도는 높은편이고 잘 정리해두기 위해서 작성
DP 알고리즘을 위한 조건
- Overlapping Subproblems 겹치는 부분 문제
큰 문제의 해답을 구하는 과정에서 동일한 하위값이 반복되어 나타남
ex) 예를 들어, 피보나치 수열을 재귀적으로 계산한 경우 f(5) = f(4) + f(3) 이고, f(4) = f(3)+f(2) 이다.
여기서 f(3)이 겹치는 것이 동일한 하위값 반복
- Optimal Substructure 최적 부분 구조
하위문제의 최적 부분이 전체 문제의 최적부분과 같다.
ex) A->D(A->B->C->D)로 가는 최단거리의 경로가 있다고 할때 반드시 A->C(A->B->C)로 가는 경로도 최단거리여야 한다.
문제
피보나치 수는 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
적용 알고리즘
재귀 호출 시 발생하는 시간 초과를 해결하기 위해 동적 계획법(DP)을 적용. 반복문을 사용하여 0부터 n까지의 피보나치 수를 배열에 순차적으로 저장하는 상향식(Bottom-up) 방식으로 구현함
문제 접근 방식
-
먼저 배열을 정의하고 반복문을 통해서 값 저장
-
스택 오버플로우를 고려하여 단순한 n번째 피보나치 수열을 반환하는 것이 아닌 연속된 두 배열의 합의 나머지값을 저장함으로서 해결
기본코드 및 주석설명
class Solution {
public int solution(int n) {
int[] dp = new int[n+1];
dp[0]=0;
dp[1]=1;
for(int i=2;i<n+1;i++){
dp[i] = (dp[i-1]+dp[i-2])%1234567;
}
return dp[n];
}
}시간 복잡도 공간복잡도
시간 복잡도 : 반복문 한번 수행했기때문에O(n)
공간 복잡도 : O(n)
