dynamic-programming 튜토리얼
동적 프로그래밍 시작하기

비고

동적 프로그래밍 소개

동적 프로그래밍 은 솔루션을 하위 문제와 결합하여 문제를 해결합니다. 이것은 문제가 분리 된 하부 문제로 분할되고, 하부 문제가 재귀 적으로 풀린 다음 원래의 문제의 해결책을 찾기 위해 결합 된 분할 및 정복 방법과 유사 할 수 있습니다. 대조적으로 동적 프로그래밍은 하위 문제가 겹칠 때 적용됩니다. 즉 하위 문제가 하위 문제를 공유 할 때 적용됩니다. 이러한 맥락에서 Divide-and-Conquer 알고리즘은 필요한 것보다 더 많은 작업을 수행하여 공통 하위 문제를 반복적으로 해결합니다. 동적 프로그래밍 알고리즘은 각 하위 문제를 한 번만 해결 한 다음 해당 답변을 표에 저장하므로 각 하위 문제를 해결할 때마다 대답을 다시 계산하지 않아도됩니다.

예를 살펴 보겠습니다. 이탈리아 수학자 Leonardo Pisano Bigollo ( 피보나치로 널리 알려진) 는 토끼 인구 의 이상적인 성장을 고려하여 숫자 시리즈를 발견했습니다. 시리즈는 :

1, 1, 2, 3, 5, 8, 13, 21, ......

처음 두 개 이후의 모든 숫자는 앞의 두 숫자의 합계입니다. 이제 우리에게 n 번째 피보나치 수를 반환하는 함수 F (n) 을 공식화 해 봅시다. 즉,

F(n) = nth Fibonacci Number

지금까지 우리는 그것을 알고있었습니다,

F(1) = 1
F(2) = 1
F(3) = F(2) + F(1) = 2
F(4) = F(3) + F(2) = 3

우리는 다음과 같이 일반화 할 수 있습니다.

F(1) = 1
F(2) = 1
F(n) = F(n-1) + F(n-2)

이제 재귀 함수로 쓰고 싶다면 F(1) 과 F(2) 를 기본 케이스로 사용합니다. 그래서 피보나치 함수는 다음과 같습니다 :

Procedure F(n):                //A function to return nth Fibonacci Number
if n is equal to 1
    Return 1
else if n is equal to 2
    Return 1
end if
Return F(n-1) + F(n-2)

이제 F(6) 를 호출하면 F(5) 와 F(4) 가 호출되어 더 많이 호출합니다. 이것을 그래픽으로 표현 해보자.

그림에서 F(6) 은 F(5) 와 F(4) 호출 함을 알 수 있습니다. 이제 F(5) 는 F(4) 와 F(3) 호출합니다. 계산 후 F(5) , 우리는 확실히에 의해 호출 된 모든 기능을 말할 수 F(5) 이미 계산되었습니다. 즉, 우리는 이미 F(4) 계산했습니다. 그러나 우리는 F(6) 의 오른쪽 자식이 나타내는 것처럼 F(6) F(4) 를 다시 계산합니다. 다시 계산해야합니까? 우리가 할 수있는 일은 F(4) 의 값을 계산하면 dp 라는 배열에 저장하고 필요할 때 다시 사용합니다. dp 배열을 -1 (또는 계산에 포함되지 않는 값)으로 초기화합니다. 그런 다음 수정 된 F (n) 이 다음과 같이 표시되는 F (6)를 호출합니다.

Procedure F(n):
if n is equal to 1
    Return 1
else if n is equal to 2
    Return 1
else if dp[n] is not equal to -1            //That means we have already calculated dp[n]
    Return dp[n]
else
    dp[n] = F(n-1) + F(n-2)
    Return dp[n]
end if

이전과 동일한 작업을했지만 단순한 최적화 작업 만 수행했습니다. 즉, 우리는 암기 기법을 사용했습니다. 처음에는 dp 배열의 모든 값이 -1이 됩니다. F(4) 가 호출되면 비어 있는지 확인합니다. -1 을 저장 하면 값을 계산하여 dp [4] 에 저장합니다. -1이 아닌 값이 저장되면 값을 이미 계산했음을 의미합니다. 그래서 우리는 단순히 그 값을 돌려 줄 것입니다.

메모 작성을 사용한이 간단한 최적화를 동적 프로그래밍 이라고합니다.

동적 프로그래밍을 사용하면 몇 가지 특성이있는 문제를 해결할 수 있습니다. 이것들은:

• 문제 :
  DP 문제는 하나 이상의 하위 문제로 나눌 수 있습니다. 예 : F(4) 는 더 작은 하위 문제 F(3) 과 F(2) 로 나눌 수 있습니다. 하위 문제는 우리의 주요 문제와 유사하므로 동일한 기술을 사용하여 해결할 수 있습니다.
• 겹치는 부분 문제 :
  DP 문제에는 중복되는 하위 문제가 있어야합니다. 즉, 같은 기능이 두 번 이상 호출되는 공통 부분이 있어야합니다. 예 : F(5) 및 F(6) 은 F(3) 및 F(4) 를 공통으로 포함합니다. 이것이 배열에 값을 저장 한 이유입니다.

• 최적 하부 구조 :
  함수 g(x) 를 최소화하라는 요청을 받았다고 가정 해 봅시다. g(x) 의 값은 g(y) 와 g(z) 에 의존한다는 것을 알고 있습니다. 이제 g(y) 와 g(z) 모두 최소화하여 g(x) 를 최소화 할 수있는 경우에만 문제가 최적 하부 구조를 갖는다 고 말할 수 있습니다. 경우 g(x) 단지 최소화함으로써 최소화된다 g(y) 최소화 또는 최대화 경우 g(z) 아무런 영향이없는 g(x) ,이 문제는 최적의 하부가없는이. 간단히 말하면, 문제의 최적해가 그 하부 문제의 최적해로부터 발견 될 수 있다면, 문제는 최적 하부 구조 속성을 가질 수 있다고 말할 수 있습니다.

동적 프로그래밍의 상태 이해

예를 들어 설명해 보겠습니다. n 개의 항목에서 r 개의 항목을 선택할 수있는 방법은 무엇입니까? 너는 그것이에 의해 표시된다는 것을 안다. . 이제 단일 항목을 생각해보십시오.

• 항목을 선택하지 않으면 나머지 n-1 항목에서 r 개의 항목을 가져와야합니다. .
• 항목을 선택하면 나머지 n-1 항목에서 r-1 개 항목을 가져와야합니다. .

이 둘의 합계는 우리에게 총 방법 수를 제공합니다. 그건:

nCr(n,r) 을 n 및 r 을 매개 변수로 사용하여 , 우리는 위에서 언급 한 관계를 다음과 같이 작성할 수 있습니다.

nCr(n,r) = nCr(n-1,r) + nCr(n-1,r-1)

이것은 재귀 관계입니다. 종료하려면 기본 사례를 결정해야합니다. 우리는, 과 . 이 두 가지를 기본 사례로 사용하여 될거야:

Procedure nCr(n, r):
if r is equal to 1
    Return n
else if n is equal to r
    Return 1
end if
Return nCr(n-1,r) + nCr(n-1,r-1)

프로 시저를 그래픽으로 보면, 몇 번 이상 호출 된 재귀가 있음을 알 수 있습니다. 예를 들어, n = 8 및 r = 5를 취하면 다음을 얻습니다.

배열 dp를 사용하여이 반복 호출을 피할 수 있습니다. 매개 변수가 2 개 이므로 2D 배열이 필요합니다. 우리는 -1로 dp 배열을 초기화 할 것입니다. -1 은 값이 아직 계산되지 않았 음을 나타냅니다. 우리의 절차는 다음과 같습니다 :

Procedure nCr(n,r):
if r is equal to 1
    Return n
else if n is equal to r
    Return 1
else if dp[n][r] is not equal to -1        //The value has been calculated
    Return dp[n][r]
end if
dp[n][r] := nCr(n-1,r) + nCr(n-1,r-1)
Return dp[n][r]

결정 우리는 n 과 r 이라는 두 개의 매개 변수가 필요했습니다. 이러한 매개 변수를 상태 라고 합니다 . 우리는 단순히 상태 수가 dp 배열의 차원 수를 결정한다는 것을 추론 할 수 있습니다. 배열의 크기는 우리의 필요에 따라 바뀔 것입니다. 우리의 동적 프로그래밍 알고리즘은 다음과 같은 일반적인 패턴을 유지합니다 :

Procedure DP-Function(state_1, state_2, ...., state_n)
Return if reached any base case
Check array and Return if the value is already calculated.
Calculate the value recursively for this state
Save the value in the table and Return

상태 결정은 동적 프로그래밍의 가장 중요한 부분 중 하나입니다. 그것은 문제를 정의하고 계산을 최적화하는 매개 변수의 수로 구성되며 전체 문제를 최적화 할 수 있습니다.

DP 솔루션 구축

다이나믹 프로그래밍 (DP)을 사용하여 몇 가지 문제를 해결하더라도 문제가 될 수 있습니다. 그러나 인생의 다른 모든 것들처럼, 연습은 당신을 더 잘합니다. 이를 염두에두고 우리는 DP 문제에 대한 해결책을 만드는 과정을 살펴볼 것입니다. 이 항목에 대한 다른 예는 DP가 무엇이며 어떻게 작동하는지 이해하는 데 도움이됩니다. 이 예에서는 처음부터 DP 솔루션을 찾는 방법을 이해하려고 노력할 것입니다.

반복 VS 재귀 :
DP 솔루션을 구축하는 데는 두 가지 기술이 있습니다. 그들은:

• 반복 (for-cycles 사용)
• 재귀 (재귀 사용)

예를 들어, 두 문자열 s1 과 s2 의 Longest Common Subsequence 길이를 계산하는 알고리즘은 다음과 같습니다.

Procedure LCSlength(s1, s2):
Table[0][0] = 0
for i from 1 to s1.length
    Table[0][i] = 0
endfor
for i from 1 to s2.length
    Table[i][0] = 0
endfor
for i from 1 to s2.length
    for j from 1 to s1.length
        if s2[i] equals to s1[j]
            Table[i][j] = Table[i-1][j-1] + 1
        else
            Table[i][j] = max(Table[i-1][j], Table[i][j-1])
        endif
    endfor
endfor
Return Table[s2.length][s1.length]

이것은 반복적 인 솔루션입니다. 이런 식으로 코딩 된 몇 가지 이유가 있습니다.

• 반복은 재귀보다 빠릅니다.
• 시간과 공간의 복잡성을 쉽게 판단 할 수 있습니다.
• 소스 코드가 짧고 깨끗합니다.

소스 코드를 살펴보면 어떻게 그리고 왜 작동하는지 이해할 수 있지만이 솔루션을 찾는 방법을 이해하는 것은 어렵습니다. 그러나 위에서 언급 한 두 가지 접근법은 서로 다른 두 가지 의사 코드로 변환됩니다. 하나는 반복 (상향식)을 사용하고 다른 하나는 재귀 (하향식) 방식을 사용합니다. 후자는 메모 기법으로 알려져 있습니다. 그러나 두 가지 솔루션은 다소 비슷하며 하나는 쉽게 다른 솔루션으로 변형 될 수 있습니다. 이 예제에서는 문제에 대한 재귀 적 해결책을 찾는 방법을 보여줍니다.

예제 문제 :
예를 들어 N ( 1, 2, 3, ..., N ) 개의 와인이 선반에 나란히 놓여 있다고 가정 해 봅시다. i th 와인의 가격은 P [i] 입니다. 와인의 가격은 매년 증가합니다. i 번째 와인의 가격이 될 것이다 (Y)이 연도에 년 1한다고 가정 해 * 와인의 Y = * P는 [I]의 가격. 당신은 가지고있는 와인을 판매하고 싶지만, 올해부터 정확히 1 년에 1 개의 와인을 판매해야합니다. 다시 한 번 매년 가장 왼쪽 또는 가장 오른쪽의 와인 만 판매 할 수 있으며 와인을 다시 배열 할 수 없습니다. 즉, 와인을 처음부터 순서대로 유지해야합니다.

예를 들어 선반에 4 개의 와인이 있고 그 가격이 (왼쪽에서 오른쪽으로)라고 가정 해 봅시다.

+---+---+---+---+
| 1 | 4 | 2 | 3 |
+---+---+---+---+

최적의 해결책은 1 -> 4 -> 3 -> 2 순서로 와인을 판매하는 것입니다. 이렇게하면 다음과 같은 총 이익을 얻을 수 있습니다.

욕심 많은 접근법 :
잠시 브레인 스토밍을 한 후에는 비싼 와인을 가능한 한 늦게 팔 수있는 해결책을 제시 할 수도 있습니다. 그래서 당신의 욕심쟁이 전략은 다음과 같습니다 :

Every year, sell the cheaper of the two (leftmost and rightmost) available wines.

이 전략은 두 와인의 가격이 같을 때해야 할 일을 언급하지는 않지만, 전략은 옳다고 생각합니다. 그러나 불행히도, 그것은 아닙니다. 와인 가격이 다음과 같은 경우 :

+---+---+---+---+---+
| 2 | 3 | 5 | 1 | 4 |
+---+---+---+---+---+

욕심 많은 전략은 1 -> 2 -> 5 -> 4 -> 3 순서로 판매하여 총 이익을 얻습니다.

그러나 와인을 1 -> 5 -> 4 -> 2 -> 3 순서로 판매하면 총 이익은 다음과 같이 향상됩니다.

이 예제는 문제가 처음 보이는 것처럼 쉽지 않다는 것을 확신시켜야합니다. 그러나 동적 프로그래밍을 사용하여 해결할 수 있습니다.

역 추적 :
백 트랙 솔루션을 찾는 문제에 대한 메모 솔루션을 제시하는 것이 편리합니다. 백 트랙 솔루션은 문제에 대한 모든 유효한 응답을 평가하고 가장 적합한 답변을 선택합니다. 대부분의 문제에 대해 그러한 해결책을 제시하는 것이 더 쉽습니다. 백 트랙 솔루션에 접근 할 때 따라야 할 세 가지 전략이 있습니다.

1. 재귀를 사용하여 해답을 계산하는 함수 여야합니다.
2. return 문으로 응답을 리턴해야 합니다.
3. 모든 비 로컬 변수는 읽기 전용으로 사용해야합니다. 즉 함수는 로컬 변수와 해당 인수 만 수정할 수 있습니다.

예를 들어, 가장 왼쪽 또는 가장 오른쪽의 와인을 판매하고 재귀 적으로 계산하여 더 나은 와인을 반환하려고합니다. 백 트랙 솔루션은 다음과 같습니다.

// year represents the current year
// [begin, end] represents the interval of the unsold wines on the shelf
Procedure profitDetermination(year, begin, end):
if begin > end                  //there are no more wines left on the shelf
    Return 0
Return max(profitDetermination(year+1, begin+1, end) + year * p[begin], //selling the leftmost item
           profitDetermination(year+1, begin, end+1) + year * p[end])   //selling the rightmost item

profitDetermination(1, 0, n-1) 사용하여 프로 시저를 호출하면 n 은 총 와인 수이며, 여기서 답을 반환합니다.

이 솔루션은 단순히 와인을 판매하는 모든 유효한 조합을 시도합니다. 처음에 n 개의 와인이 있다면, 가능성. 지금 우리가 정답을 얻었지만 알고리즘의 시간 복잡도는 기하 급수적으로 증가합니다.

올바르게 작성된 백 트랙 기능은 항상 잘 설명 된 질문에 대한 대답을 나타냅니다. 이 예에서 프로 시저 profitDetermination 은 배열 p에 저장된 가격의 와인을 판매 할 때 얻을 수있는 가장 좋은 이익은 무엇입니까? 현재 연도가 연도이고 판매되지 않은 와인의 간격이 [시작될 때 , 끝], 포함합니까? 백 트랙 기능에 대해 항상 그런 질문을 만들어 올바른 결과를 얻었는지 확인하고 정확히 무엇을하는지 이해해야합니다.

결정 상태 :
State 는 DP 솔루션에서 사용되는 매개 변수의 수입니다. 이 단계에서는 함수에 전달하는 인수 중 중복되는 인수에 대해 고려해야합니다. 즉 다른 인수에서 인수를 구성하거나 필요하지 않습니다. 그러한 인수가 있으면 함수에 인수를 전달할 필요가 없으며 함수 내에서 인수를 계산합니다.

위에 표시된 예제 함수 profitDetermination 에서 인수 year 는 중복됩니다. 이미 판매 된 와인의 수에 1을 더한 것과 같습니다. 처음부터 총 와인 수에서 판매하지 않은 와인 수 + 1을 사용하여 결정할 수 있습니다. 와인의 총 수 n 을 전역 변수로 저장하면 함수를 다음과 같이 다시 쓸 수 있습니다.

Procedure profitDetermination(begin, end):
if begin > end
    Return 0
year := n - (end-begin+1) + 1        //as described above
Return max(profitDetermination(begin+1, end) + year * p[begin],
           profitDetermination(begin, end+1) + year * p[end])

우리는 또한 유효한 입력으로부터 얻을 수있는 매개 변수의 가능한 값의 범위에 대해 생각할 필요가 있습니다. 이 예에서 각 begin 및 end 매개 변수는 0 에서 n-1 까지의 값을 포함 할 수 있습니다. 유효한 입력에서는 begin <= end + 1 기대 begin <= end + 1 . 있을 수 있습니다 O(n²) 다른 인수는 우리의 함수를 호출 할 수 있습니다.

메모 :
우리는 이제 거의 끝났습니다. 시간 복잡성으로 백 트랙 솔루션을 변환하려면 시간 복잡성을 가진 메모 솔루션으로 , 우리는 많은 노력을 필요로하지 않는 약간의 트릭을 사용할 것입니다.

위에서 언급 한 것처럼 우리의 함수를 호출 할 수있는 다른 매개 변수. 다시 말해, 우리가 실제로 계산할 수있는 다른 것들. 그럼 어디 있니? 시간의 복잡성은 무엇으로부터 왔으며 계산은 무엇입니까?

답은 다음과 같습니다. 지수 적 시간 복잡도는 반복적 인 재귀에서 비롯되며, 그 때문에 반복되는 동일한 값을 계산합니다. n = 20 와인의 임의의 배열에 대해 위에서 언급 한 코드를 실행하고 인수 begin = 10 및 end = 10에 대해 호출 된 함수의 횟수를 계산하면 숫자 92378이 됩니다. 그것은 동일한 답변을 여러 번 계산하는 데 엄청난 시간 낭비입니다. 이를 개선하기 위해 우리가 할 수있는 것은 값을 계산 한 후에 값을 저장하는 것입니다. 그리고 함수가 이미 계산 된 값을 요구할 때마다 전체 재귀를 다시 실행할 필요가 없습니다. 우리는 배열 dp [N] [N]을 가질 것이고, -1 (또는 우리 계산에 포함되지 않는 값)로 초기화 할 것입니다. -1 은 값이 아직 계산되지 않았 음을 나타냅니다. 배열의 크기는 시작 과 끝 의 가능한 최대 값에 의해 결정됩니다. 우리는 배열에 특정 시작 값과 끝 값의 해당 값을 저장할 것이기 때문입니다. 우리의 절차는 다음과 같습니다.

Procedure profitDetermination(begin, end):
if begin > end
    Return 0
if dp[begin][end] is not equal to -1                //Already calculated
    Return dp[begin][end]
year := n - (end-begin+1) + 1
dp[begin][end] := max(profitDetermination(year+1, begin+1, end) + year * p[begin],
           profitDetermination(year+1, begin, end+1) + year * p[end])
Return dp[begin][end]

이것이 우리가 필요로하는 DP 솔루션입니다. 우리의 아주 간단한 트릭으로 솔루션이 실행됩니다. 시간이 있기 때문에 우리의 함수가 호출 될 수있는 다른 매개 변수와 각 함수에 대해 함수는 복잡성.

여름 :
DP를 사용하여 해결할 수있는 문제를 식별 할 수있는 경우 다음 단계를 사용하여 DP 솔루션을 구성하십시오.

• 백 트랙 기능을 만들어 정답을 제공하십시오.
• 중복 된 인수를 제거하십시오.
• 함수 매개 변수의 가능한 최대 값 범위를 예측하고 최소화하십시오.
• 하나의 함수 호출의 시간 복잡성을 최적화하려고 시도하십시오.
• 값을 두 번 계산할 필요가 없도록 값을 저장하십시오.

DP 솔루션의 복잡성은 다음과 같습니다. 각 호출의 시간 복잡성으로 함수를 호출 할 수있는 가능한 값 범위 .