다이나믹프로그래밍

다이나믹 프로그래밍이란

다이나믹 프로그래밍은 큰 문제를 작은 문제로 나눠서 푸는 알고리즘이다.
(다이나믹 프로그래밍에서 다이나믹은 아무 의미가 없으므로, 동적 이라는 말에 굳이 집중할 필요는 없다)

다이나믹 프로그래밍은 아래 두 가지 속성을 만족해야 한다.

  1. Overlapping Subproblem
    • 문제를 작은 문제들로 쪼갤 수 있어야 함
    • 작은 문제들로 쪼개진다고 무조건 DP는 아니고, 작은(부분)문제들이 겹쳐야 함
    • 큰 문제와 작은 문제를 같은 방법으로 풀 수 있음
    • 큰 문제냐 작은 문제냐는 상대적인 개념이다
  2. Optimal Substructure
    • 문제의 정답을 작은 문제의 정답에서 구할 수 있어야 함
    • 같은 문제들은 구할 때 마다 정답이 같아야 한다

Optimal Substructure를 만족하는 구할 때 마다 정답이 같은 문제들은 어딘가에 메모해놓고 다시 사용함으로써 계산 속도를 월등히 높일수가 있는데, 이를 Memoization 이라고 한다.
컴퓨터에서는 배열에 저장해 놓을 수 있다.

정리하자면,

  1. 작은 문제가 계속 반복되고 있어야 한다
  2. 작은 문제의 정답을 합하는 것으로 문제의 정답을 구할 수 있어야 한다
  3. 작은 문제는 구할 때 마다 메모이제이션 해야 한다

다이나믹 프로그래밍 문제를 푸는 방법

  1. 메모이제이션 할 배열에 뭘 저장할 것인가?

    대부분의 다이나믹 문제는 문제에서 구하라고 한 것을 배얄에 넣어주면 된다

  2. 어떻게 저장할 값을 구할 것인가?

    점화식이 생기게 됨

  3. 점화식으로 메모이제이션 배열을 점점 채워나가는 식으로 문제를 풀어나감
  • Top-down
    • 문제를 작은 문제들로 나눈다
    • 작은 문제를 푼다
    • 작은 문제들을 합쳐서 큰 문제를 푼다
    • 대체적으로 재귀를 사용한다

    큰 문제의 답을 작은 문제에게 물어보는 방식이라고 보면 될 듯
    그러므로 대체적으로 재귀 형태가 사용되는 것이다

  • Bottom-Up
    • 작은 문제부터 차례대로 푼다
    • 문제의 크기를 조금씩 크게 만들면서 조금씩 푼다
    • 작은 문제를 풀면서 왔기 때문에 큰 문제는 항상 풀 수 있다
    • 계속하다보면 문제를 풀 수 있다
    • 대체적으로 for문을 사용한다

    메모이제이션할 값을 아래서부터 순서대로 채운다고 생각하면 될 듯
    재귀 호출하지 않아서 시간과 메모리 사용을 줄일 수 있다

예시


3으로 나누면 가장 빨리 문제를 작게 만들 수 있겠다
하지만 그것이 문제를 항상 푸는 정답이 아니다
그러므로 다이나믹 프로그래밍을 사용해야 한다

여러가지 값을 다 가져온 다음에 최소값을 가져와야 하므로?
브루트포싱을 사용해야한다고 생각할수도 있지 않나?
브루트포싱이 나오면 dp를 생각해볼수 있는건가?

  1. D[n]에 뭐가 저장되어야 하는가?

대부분의 다이나믹 문제는 문제에서 구하라고 한 것을 그냥 D[n]에 넣어주면 된다
연산을 사용하는 횟수의 최소값을 출력하라고 했으니 그 값을 그대로 저장하자

  1. 그러면 N에 어떤 연산을 할 수 있는가?
    3으로 나누어서 1로 만드는 횟수를 넣을수도 있고,
    2로 나누어서 1로 만드는 횟수를 넣을수도 있고,
    1을 빼서 1로 만드는 횟수를 넣을수도 있다.
  2. 그렇다면 그것으로 어떻게 최소값을 구할것인가?
    몇번이고 호출해서 뭐가 더 최소인지 구하면 되는건데
    거기서 메모이제이션에 사용된 값을 쓰면 되는 것이고

d[n] = d[n/3] + 1(연산의 횟수가 1회 이므로)
d[n] = d[n/2] + 1

if(n%3)

작은 문제 : 3으로 나누어서 1로 되는 경우
이것들을 합해서 최종 결과를 도출하는 것

N을 N/3으로 만드는 연산 1회
N/3을 1로 만드는 연산을 구해야 하는데, 그건 D[N/3]에서 구할 수 있다

그러므로 총 연산의 횟수는 D[N/3] + 1 회가 된다

D[n]을 구하는 방법은 현재 3가지가 있고, 이 3가지 중 최소값을 D[n]에 넣으면 된다