DP 다이나믹 프로그래밍

[heerucan]

이론설명

• 큰 문제를 작은 문제로 나눠서 푸는 알고리즘

• 단, 조건이 있음

  1. 겹치는 부분문제
  2. 문제의 정답을 작은 문제의 정답에서 구할 수 있을 때

• Memoization : 정답을 한 번 구했으면, 어딘가에 메모해둔다. → 즉, 코드로는 배열에 저장하는 것이다.

• 피보나치 (Fn = Fn-1 + Fn-2) 근데 n ≥ 2 부터 가능
  

  • 기존에는 바로 저 네모박스 친 거를 리턴했는데 해당 값을 memoization 기법을 통해 배열에 저장한다.

    즉, 메모하는 코드임

  • 왜냐하면, f5 = f3 + f4인데, 여기서 f4 = f2 + f3이라서 f3이 중복되니까, 해당 값을 저장해두는 것임

  • 그래서 만약 예전에 계산한 값이면 아래 네모박스처럼 메모해둔 (배열에 저장한 값) 값을 가져오면 됨
    

• 탑다운 : 큰문제 → 작은문제로 나누기 (재귀함수)
  

  시간복잡도 계산하기

  • 채워야 하는 칸의 수 (메모 배열에 총 몇 개의 수가 채워질 것이냐?!!) * 1칸을 채우는 복잡도
    • 피보나치의 경우, N개의 수
    • 그리구 저기 memo[n] 이거가 이제 보면 n-1 + n-2 덧셈으로 이루어져서 O(1)로 보면 되고
    • 최종적으로 N * O(1) = O(n)

• 바텀업 : 작은문제 → 큰문제로 (for문)

  작은 문제들을 다 풀면 → 반드시 큰문제도 풀 수 있는 구조야!

  언젠가는 그래서 풀어야 하는 문제를 풀 수 있게 됨
  

---

문풀전략

1. d[i]에 뭐가 들어갈 지 정의해줘야 함

   d[i] = i번째 피보나치 수

2. i 번째 피보나치 수를 구하려면, i-1번째 피보나치 수랑 i-2번째 피보나치 수를 구해야 하는데

   d[i-1] = i-1번째 피보나치 수

   d[i-2] = i-2번째 피보나치 수

   d[i] = d[i-1] + d[i-2]

3. 보통 바텀업으로 풀자!!!!!!!

---

문제풀이

1. 1로 만들기

   • 최솟값을 구해야 하니까 3으로 나누는 걸 가장 많이 해야 하는 것을 캐치!

   • D[N]에 어떤 값이 저장되냐? → 문제에서 구하라는 값을 넣어주면 됨

     즉, N을 1로 만드는데 필요한 연산의 최솟값이 저장된다.
     

     • 첫 번째 N이 3으로 나눠떨어지면 3으로 나누는 과정 ⇒ N/3 → 1로 만드는 과정

       • N → N/3 은 연산이 1번
       • N/3은 D[N/3]이니까
       • 최종적으로 위 과정에서 필요한 연산 횟수는 **D[N/3]+1**

     • ~~ ⇒ N/2 → 1로 만드는 과정

       • N → N/2는 연산이 1번
       • N/2는 D[N/2]
       • 최종적으로 위 과정에서 필요한 연산 횟수는 **D[N/2]+1**

     • 1 빼기

       • N → N-1은 연산이 1번
       • N-1은 D[N-1]
       • 최종적으로 연산횟수는 D[N-1] + 1
       • 

     • 최솟값을 구해야 하기 때문에

       • D[N] = min(D[N/3]+1, D[N/2]+1, D[N-1]+1)