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

  • 큰 문제를 작은 문제로 나눠서 푸는 알고리즘
  • 다이나믹 프로그래밍은 작게 나눈 문제끼리 중복되지만 분할정복은 그렇지 않다는 점에서 차이가 있다.

DP로 해결가능한 문제의 속성

  1. Overlapping Subproblem
    • 큰 문제와 작은 문제를 같은 방법으로 풀 수 있다.
    • 문제를 작은 문제로 쪼갤 수 있다.
    • 예: 피보나치 수열 Fn = Fn-1 + Fn-2
  2. Optimal Substructure
    • 문제의 정답을 작은 문제의 정답에서 구할 수 있다.
    • 문제의 크기에 상관없이 어떤 한 문제의 정답은 일정하다.
  • Optimal Substructure를 만족하기 때문에, 같은 문제는 구할 때마다 정답이 같으므로, 다이나믹 프로그래밍에서 각 문제는 한 번만 푼다.
  • 한 번 구한 정답은 배열에 저장해놓는 식으로 메모하듯이 구현하는 것을 Memoization이라고 한다.
  • 점화식을 만들어 풀이
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//memoization을 적용한 피보나치 수를 구하는 함수
//Top-down
//O(N)
int memo[100];
int fibonacci(int n){
    if(n <= 1){
        return n;
    }
    else{
        if(memo[n] > 0){
            return memo[n];
        }
        memo[n] = fibonacci(n-1) + fibonacci(n-2);
        return memo[n];
    }
}

구현 방식

  1. Top-down
    • 재귀로 푸는 방식
  2. Bottom-up
    • 작은 문제부터 차례대로 푸는 방식
    • 반복문으로 구현
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      //
      int d[100];
      int fibonacci(int n){
          d[0];
          d[1];
          fof(int i = 2; i < n; i++){
              d[i] = d[i-1] + d[i-2];
          }
          return d[n];
      }
  • 재귀로 푸는 경우 스택오버플로우를 조심해야하나 구현이 잘된 경우 발생하지 않음
  • 둘 중에 편한 방식 하나를 골라 연습

관련 연습문제

  • 1로 만들기 (1463)
  • 2xn 타일링 (11726)
  • 2xn 타일링2 (11727)
  • 1, 2, 3 더하기 (9095)
  • 카드 구매하기 (11052)
  • 카드 구매하기2 (16194)
  • 1, 2, 3 더하기 5 (15990)
  • 쉬운 계단 수 (10844)
  • 이친수 (2193)
  • 가장 긴 증가하는 부분 수열 (11053)
  • 가장 긴 증가하는 부분 수열 4 (14002)
  • 연속합 (1912)
  • 제곱수의 합 (1699)
  • 합분해 (2225)
  • …
  • 1, 2, 3 더하기 3 (15988)
  • RGB거리 (1149)
  • 동물원 (1309)
  • 오르막 수 (11057)
  • 스티커 (9465)
  • 포도주 시식 (2156)
  • 정수 삼각형 (1932)
  • 가장 큰 증가 부분 수열 (11055)
  • 가장 긴 감소하는 부분 수열 (11722)
  • 가장 긴 바이토닉 부분 수열 (11054)
  • 연속합 2 (13398)
  • 타일 채우기 (2133)
  • …
  • 동물원 (1309)
  • RGB거리 2 (17404)
  • 합분해 (2225)