[Algorithm] 동적 계획법 (DP)

in Algorithm

Elice Algorithm Code Challenge - Day 7 (동적 계획법)

목차

  1. Dynamic Programming 정의
  2. DP의 종류
  3. DP 사용조건
  4. DP 유의점

동적 계획법 (DP, Dynamic Programming)

  • 예시 문제 1
    • 1000원짜리 커피를 500원짜리 동전과 100원짜리 동전만 사용하여 계산하려고 한다.
    • 동전을 가장 적게 사용하여 계산하려고 할 때, 필요한 동전의 최소 개수는?
    • (단, 동전은 무수히 많다.)
    • Solution
      • (500 * 2) VS (500 * 1 + 100 * 5) VS (100 * 10)
        • 그리디 알고리즘으로 해결 가능
  • 예시 문제 2
    • 23원짜리 커피를 5원짜리 동전과 2원짜리 동전만 사용하여 계산하려고 한다.
    • 동전을 가장 적게 사용하여 계산하려고 할 때, 필요한 동전의 최소 개수는?
    • (단, 동전은 무수히 많다.)
    • Solution
      • 그리디 알고리즘으로 해결 불가능
      • 그리디 알고리즘을 적용할 수 잇는 조건 중 하나인 최적 부분 구조 조건을 만족하지 않기 때문
        • 지역적으로 최적이 전역적으로도 최적이 아님

Dynamic Programming 정의

  • 이전에 계산한 값을 재사용하여, 하나의 문제를 한 번만 풀게 하는 알고리즘 패러다임
  • Divide & Conquer과 비슷하지만, 중간 결과를 저장하여 효율성을 높인다는 점에서 차이
  • 이전에 계산해둔 값을 메모리(배열 등)에 저장해서 반복 작업을 줄이는 기법이 핵심
    • 하위 문제의 결과를 먼저 저장하고, 이를 나중에 필요할 때 사용
    • Tabulation(botton-up), Memoization(top-down)

DP의 종류

  • Top-Down DP
    • 가장 큰 문제부터 풀기 시작하여, 작은 문제들을 재귀적으로 호출하여 답을 구하는 방식
    • 주로 재귀를 통해 해결
    • ${\color{yellow}메모이제이션(Memoization)}$을 활용하여 복잡도를 줄임
    • 예시
            int fibo(int n) {
          if (n <= 2 ) return 1;
          int &ret = dp[n]

          if (ret != -1) return ret;
          return ret = fibo(n-1) + fibo(n-2)
      }
  • Botton-Up DP
    • 작은 문제들을 먼저 풀기 시작하여, 최종적으로 가장 큰 문제들을 해결하는 방식
    • 주로 반복문을 통해 해결
    • ${\color{yellow}점화식과 기저사례}$(base case)가 필요 -> ${\color{yellow}Tabulation}$
    • 예시
            for (int i = 2; i <= 40; ++i) {
          dp[i] = dp[i-1] + dp[i-2]; 
      } //점화식

DP 사용 조건

  1. 겹치는 부분(작은) 문제 (Overlapping Subproblem)
    • 어떠한 문제가 여러 개의 부분(하위) 문제(subproblem)으로 쪼갤 수 있을 대 사용
  2. 최적 부분 구조 (Optimal Substructure)
    • 문제의 정답을 작은 문제의 정답에서 구할 수 있을 때 사용
  • 예시
    • N번째 피보나치 수를 구하는 문제
      • N-1번째 피보나치 수를 구하는 문제, N-2번째 피보나치 수를 구하는 문제로 쪼갤 수 있음
      • 문제의 정답을 하위 문제의 정답의 합으로 구할 수 있음
      • 재귀로 풀 때
        • O(2^N)
        • 이미 구했던 값도 다시 계산해야 함
          • 시간 초과 발생 빛 stack overflow 가능성이 높음
      • 반복문으로 풀 때
        • O(N)
        • 기저사례와 점화식으로 구현

DP 유의점

  • 복잡한 문제의 경우, 점화식을 직접 계산해서 구해야 한다.