다이나믹 프로그래밍(Dynamic Programming)

yellong·2020년 5월 22일
0

Algorithm

목록 보기
5/11

다이나믹 프로그래밍

  • 큰 문제를 작은 문제로 나눠서 푸는 알고리즘
  • 두 가지 속성을 만족해야 다이나믹 프로그래밍으로 문제를 풀 수 있다.
    • Overlapping Subproblem(겹치는 부분/작은 문제)
    • Optimal Substructure(최적 부분 구조)

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

  • 다이나믹 프로그래밍
    • 작은 문제가 중복이 되어도 된다.
  • 분할 정복(Divide and Conquer)
    • 작은 문제가 중복이 되면 안된다.

Overlapping Subproblem

  • 피보나치 수
    • F0 = 0
    • F1 = 1
    • Fn = Fn-1 + Fn-2 (n >= 2)
    • 문제: N번째 피보나치 수를 구하는 문제
    • 작은 문제: N-1번째 피보나치 수를 구하는 문제
  • 큰 문제와 작은 문제를 같은 방법으로 풀 수 있으며,
  • 문제를 작은 문제로 쪼갤 수 있다.
  • 재귀 사용

Optimal Substructure

  • 문제의 정답을 작은 문제의 정답에서 구할 수 있다.
  • 예) 서울에서 부산을 가는 가장 빠른 길이 대전과 대구를 순서대로 거쳐야 한다면, 대전에서 부산을 가는 가장 빠른 길은 대구를 거쳐야 한다.
  • Optimal Substructure를 만족한다면, 문제의크기에 상관없이 어떤 한 문제의 정답은 일정하다.

다이나믹 프로그래밍 TIP

  • 다이나믹 프로그래밍에서 각 문제는 한 번만 풀어야 한다.
  • Optimal Substructure를 만족하기 때문에, 같은 문제를 구할 때마다 정답이 같다.
  • 따라서, 정답을 한 번 구했으면, 정답을 어디에다가 메모해놓는다.
  • 이런 메모하는 것을 코드에서는 배열에 저장하는 것으로 할 수 있다.
  • 메모를 한다고 해서, 영어로 Memorization이라고 한다.
int memo[100];
int fibonacci(int n){
  if(n<=1){
    return n;
  }else {
    //중복되게 풀 필요 없이, 단 한 번만 푸는 것!
    //Time Complexity = 문제의 개수(N) * 문제 1 개를 푸는 시간(함수의 시간 복잡도)
    if(memo[n]>0){
      return memo[n];
    }
    memo[n] = fibonacci(n-1) + fibonacci(n-2);
    return memo[n];
  }
}

다이나믹 프로그래밍 구현 방식

  • Top-down (재귀)
    • 문제를 풀어야 한다.
      • fib(n)
    • 문제를 작은 문제로 나눈다.
      • fib(n-1), fib(n-2)
    • 작은 문제를 푼다.
    • 작은 문제를 풀었으니, 이제 문제를 푼다.
  • Bottom-up (반복)
    • 문제를 크기가 작은 문제부터 차례대로 푼다.
    • 문제의 크기를 조금씩 크게 만들어서 문제를 점점 푼다.
    • 작은 문제를 풀면서 왔기 때문에, 큰 문제는 항상 풀 수 있다.
    • 반복하다보면 가장 큰 문제를 풀 수 있다.
    • 주로 반복문
int d[100];
int fibonacci(int n){
  d[0]=0;
  d[1]=1;
  for(int i=2; i<=n; i++){
    d[i] = d[i-1] + d[i-2];
  }
  return d[n];
}
  • Top-down과 Bottom-up의 시간 차이는 알 수 없으나, 재귀가 스택을 쓰기 때문에 스택오버플로를 만들어내는 경우도 있음. 단, c++과 Java의 경우는 스택오버플로우가 자주 발생하지 않음. 발생했을 경우, 내 탓.

다이나믹 문제 풀이 전략

  • 다이나믹 프로그래밍을 풀 때는 주로 점화식을 만듦.
  • 문제에서 구하려고 하는 답을 문장으로 나타낸다.
  • 예: 피보나치 수를 구하는 문제
  • N번째 피보나치 수
  • 이제 그 문장에 나와있는 변수의 개수만큼 메모하는 배열을 만든다.
  • Top-down인 경우에는 재귀 호출의 인자의 개수
  • 문제를 작은 문제로 나누고, 수식을 이용해서 문제를 표현해야 한다.

0개의 댓글