피보나치 수
문제 설명
피보나치 수는 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 이하인 자연수입니다.
해결방법
피보나치 함수는 f(n) = f(n-1) + f(n-2)로 나타낼 수 있다.
f(n-1) = f(n-2) + f(n-3)
f(n-2) = f(n-3) + f(n-4)
볼드로 표시한 함수는 중복으로 계산된다.
중복된 항들을 계산하기 위해 수많은 하위 노드들을 또 계산해야 한다. n의 값이 커지면 이미 계산 했던 값들을 다시 구하기 위해 많은 연산을 거치게 된다. 즉, 같은 함수를 계속해서 중복 호출을 하기 때문에 재귀함수로 구현을 하면 시간복잡도 O(2^n)을 갖게 된다. 이는 메모리적 관점으로는 이것이 가장 효율적일지라도 시간적으로 생각했을 때 그렇지 못하다.
그래서 DP를 이용해서 문제를 쉽게 해결할 수 있다.
+추가 나머지 연산자도 분배법칙을 만족한다.
DP, 다이나믹 프로그래밍(동적 계획법)
기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로 특정한 알고리즘이 아닌 하나의 문제해결 패러다임으로 볼 수 있다. 간단히 말해서 답을 재활용하는 것이다.
DP 문제가 성립할 조건
이럴 때 DP를 사용하면 된다. 단순 재귀코드보다 높은 효율을 갖는 코드를 설계할 수 있다.
- 최적 부분 구조(Optimal Substructure)
- 상위 문제를 하위 문제로 나눌 수 있으며 하위 문제의 답을 모아서 상위 문제를 해결할 수 있다.
- 중복되는 부분 문제(Overlapping Subproblem)
- 동일한 작은 문제를 반복적으로 해결해야 한다.
→ 그러므로, 피보나치 수열은 DP 사용조건에 만족한다.
DP 알고리즘 기법은 무엇인가?
DP 알고리즘 기법은 이미 계산된 결과(하위 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 설계함으로써 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다.
- DP 구현 방법은 일반적으로 두 가지 방식, Top-down(하향식)과 Bottom-up(상향식)으로 구성된다.
Top-down(하향식)
상위 문제를 해결하기 위해서 하위 문제를 재귀적으로 호출하여 하위 문제를 해결함으로써 상위 문제를 해결하는 방식이다. 이 때 해결해놓은 하위 문제를 저장해 놓기 위해 Memoization이 사용된다.
피보나치 함수를 만들 때 Top-down은 재귀 호출을 사용하여 구현한다
Bottom-up(상향식)
하위에서부터 문제를 해결해나가면서 먼저 계산했던 문제들의 값을 활용해서 상위 문제를 해결해나가는 방식으로 DP의 전형적인 형태는 Bottom-up이다. 여기서 사용되는 문제 결과 값 저장용 리스트는 DP 테이블이라고 부른다.
Bottom-up 방식은 반복문을 사용해서 구현한다.
메모제이션 Memoization
메모이제이션은 DP구현 방법 중 하나로, 한 번 계산한 결과를 메모리 공간에 메모하는 기법이다. 이를 사용하면 모든 부분 문제가 한 번씩만 계산된다고 보장할 수 있기 때문에 함수 호출 횟수가 엄청나게 감소함을 예상할 수 있다.
메모제이션 특징
- 같은 문제를 다시 호출 하면 메모했던 결과를 그대로 가져온다
- 값을 기록해 놓는다는 점에서 캐싱(Cachig)이라고 한다
- DP에만 국한된 개념이 아니다. 한 번 계산된 결과를 담아 놓기만 하고 DP가 아닌 다른 방식으로도 사용될 수 있다. (캐싱,메모이제이션)
피보나치 함수를 예로 들었을 때, 이미 계산된 결과를 저장하면 아래의 색칠된 노드만 계산이 처리되어 프로그램의 작업 처리속도를 크게 향상시킬 수 있다.
참고 https://loosie.tistory.com/150
풀이 코드
Top-down
public class Solution {
public int solution(int n) {
int[] memo = new int[n + 1];
for (int i = 0; i < memo.length; i++) {
memo[i] = -1;
}
memo[0] = 0;
memo[1] = 1;
return fibo(n, memo);
}
public int fibo(int n, int[] memo) {
if (n == 1 || n == 0) {
return n;
}
if (memo[n] < 0) {
memo[n] = (fibo(n - 1, memo) + fibo(n - 2, memo)) % 1234567;
return memo[n];
}
return memo[n];
}
}Bottom-up
class Solution {
public static int solution(int n) {
long answer = 0;
int[] memo = new int[n + 2];
memo[0] = 0;
memo[1] = 1;
for (int i = 2; i <= n; i++) {
memo[i] =(memo[i - 1] + memo[i - 2]) % 1234567;
}
return memo[n];
}
}