[C++] 피보나치 수 : DP(동적 계획법)

https://school.programmers.co.kr/learn/courses/30/lessons/12945

Dynamic Programming (DP, 동적 계획법)

1. 하나의 큰 문제를 여러 개의 작은 문제로 나누고, 그 결과를 저장해서 다시 큰 문제를 해결할때 저장한 값을 가져오는 방식으로 해결

   • 문제 속의 문제가 서로 종속적인 경우에 사용하고, 배열과 같은 저장 공간에 저장해서, 필요할 때마다 재활용하므로 연산 속도 향상에 도움이 된다.

2. 시간 복잡도:
   O(N^2) -> O(N) 으로 확연히 줄어듦. 이는 동일한 계산을 반복하지 않아도 되니까.

3. DP 적용 조건

   1. Overlapping subproblems: 부분 문제가 반복적으로 나타나야 한다.
      반복적으로 나타나지 않을 경우, 재사용 불가능!
   2. Optimal Substructure: 부분 문제의 최적 결과 값으로 전체 문제의 최적 결과를 낼 수 있어야 한다.

4. DP 적용 과정
   1) DP 적용 조건 확인 - 2) 변수 파악 -
   3) 변수 간 관계식 만들기 - 4) 메모하기(값 저장) -
   5) 기저 상태 파악 - 6) 구현

5. 구현 방법

   1. Bottom-Up 방식 (Tabluation 방식) - 반복문 사용
   2. Top-Down 방식 (Memoization 방식) - 재귀(Recursion) 사용

분할정복(Divide and Conquer)와 DP의 공통점과 차이점

예를 들어, 피보나치 수열을 생각해보면 f(n) = f(n-1) + f(n-2)로 관계식이 도출된다.
n이 어떤 수가 되건, n-1번째 수와 n-2번째 수를 더해야 한다. n이 5라면, 4일 때와 3일 때를 구하고, 각각의 값을 또 구하기 위해 (2일 때, 3일 때) + (1일 때, 2일 때)로 반복적으로 내려가야 한다.
즉, n이 어떤 수가 되든,그 하위의 수를 구하는 부분은 중복적으로 나타난다.

따라서, 병합 정렬은 분할 정복으로, 피보나치 수열은 동적 프로그래밍(DP)로 해결이 가능하다!

정답 코드

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

int solution(int n) {
    int answer = 0;
    int arr[100001];
    
    // F(n)은 이전 2개의 state 합
    arr[0] = 0;
    arr[1] = 1;
    
    for (int i = 2; i <= n; i++) {

        arr[i] = (arr[i-1] + arr[i-2]) % 1234567;
    }

    answer = arr[n];
    return answer;
}

• 풀이 방식: Dynamic programming 채택

출처:
https://ansohxxn.github.io/algorithm/dp/
https://hongjw1938.tistory.com/47