Solving Skill ] 다이나믹 프로그래밍(DP)

다이나믹 프로그래밍(DP)

"한 번 계산한 문제는 다시 계산하지 않도록 하는 알고리즘"

 

 

✔  메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법.

✔  코테에서는 간단한 형태로 출제됩니다.

✔  다음 조건을 만족할 때 사용이 가능합니다.

    1. 큰 문제를 작은 문제로 나눌 수 있다.

    2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

 

 

🤡 퀵 정렬의 분할 정복과의 차이점

다이나믹 프로그래밍은 문제들이 서로 영향을 미치고 있습니다.   퀵 정렬의 pivot 원소가 자리를 잡으면 기준 원소의 위치는 더 이상 바뀌지 않습니다.

 

🌈 2가지 방식

     - Bottom up (상향식)

        : 반복문 이용 & 전형적인 DP 방식(성능이 좋을 때가 多)

     - Top down (하향식) (= 메모이제이션 기법)

        : 재귀 함수 이용

 

 

🌈 메모이제이션 기법 (= Top down )

  "한 번 구한 결과를 메모리 공간에 저장하고, 다시 호출하면 저장된 결과를 그대로 가져오는 기법"

    DP의 대표적인 예인 피보나치 수열입니다.

fib(n) {
   if n is 1 or 2, return 1;
   return fib(n-1) + fib(n-2);
}

    이때 fib 함수가 재귀적으로 실행되면서 같은 인자값에 대해서 계속해서 반복되므로, 전체 실행시간은 Ω(1.6^n)입니다.

    그러나 fib(n)의 값을 계산하자마자 저장하면(memoize), 실행시간을 Θ(n)으로 줄일 수 있습니다.

allocate array for memo, setting all entries to zero;
initialize memo[1] and memo[2] to 1;

fib(n) {
   if memo[n] is zero:
       memo[n] = fib(n-1) + fib(n-2);
   return memo[n];
}

 

 

 🌷 문제

    이것이 취업을 위한 코딩 테스트다

       유형 1 - 1로 만들기 ****

       유형 2 - 개미전사 ****

       유형 3 - 바닥 공사 *

       유형 4 - 효율적인 화폐 구성 ****

 

 

---

(Algorithm) 동적 프로그래밍(Dynamic programming) - 배낭 문제, LCS 문제, 막대기 문제