동적 프로그래밍이란 무엇입니까?

(이거 좋아하시면 BaseClass newsletter 좋아하실거에요!)

그것은 무엇이며 왜 내가 관심을 가져야 합니까?

동적 프로그래밍은 더 큰 문제를 더 작은 문제로 분해하는 프로세스입니다.

이러한 작은 문제에 대한 답을 사용하여 전체 솔루션을 보다 효율적으로 찾을 수 있습니다.

또한 '메모이제이션(memoization)'이라는 용어와 이것이 동적 프로그래밍과 어떻게 관련되는지 배울 것입니다.

어떻게 작동합니까?

동적 프로그래밍의 일반적인 예는 피보나치 수열입니다. 좋은 예이므로 여기에서도 사용할 것입니다.

피보나치 수열(및 재귀를 사용하여 계산)에 이미 익숙하다면 이 다음 섹션을 건너뛰어도 됩니다.

그것이 무엇을 의미하는지 잘 모르거나 간단히 복습하고 싶다면 계속 읽어보세요...

이것은 일련의 숫자로, 각 숫자는 앞의 두 개를 더하여 계산됩니다.



시퀀스의 6번째 숫자(위에 표시된 것처럼 8)를 프로그래밍 방식으로 계산하도록 요청한다고 상상해 보세요.

어떻게 계산하겠습니까?

다음은 바로 이 작업을 수행하는 함수에 대한 몇 가지 JavaScript 코드입니다.

function f(n) {
    // The first and second values are always 1
    if (n == 1 || n == 2)
      return 1;

    // Calculate the previous two values in the sequence
    // using this same function
    return f(n-1) + f(n-2)
  }

  // Calculate the 6th value in the sequence
  let answer = f(6)

이것은 잘 작동하지만 느립니다.

함수가 스스로를 호출하는 것을 볼 수 있습니다. 재귀적이다.

6번째 피보나치 수를 계산하려면 먼저 4번째와 5번째 피보나치 수를 계산해야 합니다.

그런 다음 각각은 이전 숫자를 계산해야 하며 이는 시퀀스의 시작 부분까지 계속 반복됩니다.

이것을 그래프로 그리면 다음과 같습니다.



여기에 중복이 많이 있음을 알 수 있습니다. 예를 들어, 시퀀스의 두 번째 값은 5번 계산됩니다!

순서에 있는 작은 숫자의 경우 이것은 그리 나쁘지는 않지만 빠르게 악화됩니다. 시퀀스의 나중 숫자의 경우 현대 컴퓨터에서도 곧 비실용적이 될 것입니다.

그럼 어떻게 하면 더 잘할 수 있을까요?

동적 프로그래밍 및 메모이제이션

이 기능을 개선할 수 있는 한 가지 방법은 진행하면서 이전 계산 결과를 저장하는 것입니다.

그렇게 하면 피보나치 수열의 각 숫자를 한 번만 계산하면 됩니다.

이것이 동적 프로그래밍의 본질입니다.

Dynamic programming is breaking the larger problem into smaller problems, and using those to get to the answer.

나중을 위해 이전 결과를 저장하여 이를 달성하기 때문에 '메모이제이션'도 사용하고 있습니다.

Memoization is storing the result of a previous calculation so that we can use it later, to make the overall algorithm more efficient.

위의 재귀적 접근 방식에서 이러한 개념을 구현할 수 있지만 '상향식' 접근 방식을 사용하면 더 쉽게 따라할 수 있습니다.

먼저 코드를 살펴보고 이것이 '상향식' 알고리즘이라고 불리는 이유에 대해 논의할 수 있습니다.

  function f(n) {
    // The first and second values are always 1
    if (n == 1 || n == 2)
      return 1

    let result = 0

    // Used to store the previous two results
    let lastButOneValue = 1
    let lastValue = 1

    // Work from item 3 of the sequence (items 1 and 2 are a 
    // special case, see above), calculate each value in turn
    for (let i = 3; i <= n; i++) {
      // Calculate this number by adding together the 
      // previous two
      result = lastValue + lastButOneValue

      // Update the values of the 
      // previous two items in the sequence
      lastButOneValue = lastValue
      lastValue = result
    }

    return result
  }

  // Calculate the 6th value in the sequence
  let answer = f(6)

여기서 우리는 필요한 수열의 숫자에 도달할 때까지 처음부터 순서대로 피보나치 수열을 계산합니다.

진행하면서 이전 값과 그 이전 값의 결과를 저장합니다.

다음 값을 얻는 것은 간단합니다. 이 두 개를 더하면 됩니다.

다음은 원래(비효율적인) 알고리즘의 그래프입니다. 그러나 이 새 버전에서 수행하는 계산만 강조 표시했습니다.



이번에는 답에서 시작하여 거꾸로 작업하는 것이 아니라 도달할 때까지 앞으로 작업하는 것을 볼 수 있습니다.
우리에게 필요한 가치.

시각화할 때 그래프의 아래쪽에서 위쪽으로 작업하므로 '하향식' 접근 방식입니다.

이 알고리즘은 훨씬 더 효율적이며 중복이 전혀 없습니다!

여기에서 몇 가지 새로운 용어를 배웠으므로 요약해 보겠습니다.

요약

우리의 최신 알고리즘은 더 큰 문제를 더 작은 문제로 나누고 그 결과를 사용하기 때문에 동적 프로그래밍을 사용합니다.
전체 답변을 얻을 수 있습니다.

또한 나중에 다시 계산하는 것을 피하기 위해 이전 단계의 결과를 저장하기 때문에 메모이제이션을 사용합니다.

그것은 '상향식' 접근 방식이었습니다. 문제를 그래프로 시각화할 때 그래프의 밑부분에서 위쪽으로 작업하기 때문입니다(덜 효율적인 알고리즘에서와 같이 하향식 대신).

더 알고 싶으십니까?

다음 링크를 확인하십시오.

A very good Stack Overflow blog post on dynamic programming

Dynamic programming in a book from MIT. Informative, but heavy going