[5] Dynamic Programming

본 글은

https://www.programiz.com/dsa/dynamic-programming

Dynamic Programming

요 글의 번역임을 알립니다.

문제가 되면 삭제합니다.

 

의역이 많습니다

Dynamic Programming 동적 계획법

  이 튜토리얼에선 동적 계획법에 대해 설명한다. 또한, 문제 해결에 있어 동적 계획법과 탐욕법(Greedy algorithm, 그리디)의 차이도 다룰 것이다.

 

  동적 계획법(Dynamic Programming)은 컴퓨터 과학(원문: 프로그래밍)의 기술이다. 이는 부분 문제 반복(overlapping subproblems)과 최적의 하위구조를 가진 프로퍼티에 대한 문제 유형들을 효울적이게 풀어나갈 수 있게 만든다.

 

  만약 어떤 문제가 더욱 작은 하위구조로 나누어질 수 있고, 이들이 중복된다면 각각의 구조에 대한 해답은 이후의 구조에 대한 참고가 될 수 있다. 이 방식에서 CPU의 효율은 향상된다. 이렇게 문제를 푸는 방식을 동적 계획법이라고 한다.

 

  이러한 문제들은 최적의 해답을 찾기 위해 같은 하위문제에 대한 값 계산을 계속 반복한다.

---

Dynamic Programming Example 동적 계획법 예시

  피보나치 수열의 5번째 수를 찾아보자. 피보나치 수열은 각각의 수가 앞의 두 수의 합인 숫자들의 나열이다. 예를 들자면 0, 1, 1, 2, 3 가 있다. 여기서 각각의 숫자는 앞의 두 수들의 합이다.

 

알고리즘

수열의 n번째일때.

1. If n <= 1, return 1.
2. Else, return 앞의 두 수를 더한다.

  5번째 수까지 피보니치 수열을 계산한다.

1. 첫 번째 수는 0이다.
2. 다음 수는 1이다.
3. 3번째 수는 0(1번)과 1(2번)의 합이다. (1)
4. 4번째 수는 3번째 수(3번)와 2번째 수(2번)의 합이다.(1+1=2)
5. 5번째 수는 4번째 수(4번)와 3번째 수(3번)의 합이다.(2+1=3)

  따라서, 우리는 0, 1, 1, 2, 3이라는 수열을 얻을 수 있다. 여기서 우리는 이전에 사용했던 결과를 다시 사용했다. 이것이을 동적 계획법적인 접근방식이라 부른다.(dynamic programming 방식)

 

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

 

---

How Dynamic Programming Works 동적 계획법의 동작방식

  동적 계획법은 하위문제의 결과를 저장함으로서 동작한다. 그 결과가 필요할 때 마다 우리는 이를 꺼내쓸 수 있고 다시 계산할 필요가 없다.

 

  이 하위 문제의 값을 저장하는 기술은 메모이제이션(memoization)이라고 불린다. 배열에 값들을 저장함으로서 이전에 이미 지나온 하위 문제들을 계산하는 시간을 절약할 수 있다.

var m = map(0 → 0, 1 → 1)
function fib(n)
    if key n is not in map m 
        m[n] = fib(n − 1) + fib(n − 2)
    return m[n]

  메모이제이션을 통한 동적 계획법은 동적 계획법을 탑-다운(top-down)적으로 접근한다. 알고리즘이 동작하는 것과 반대의 방향으로 역전한다. 가장 기본적인 문제부터 시작해 해답을 향해 접근함으로서 동적 계획법을 바텀-업(Bottom-up) 방식으로 구현할 수도 있다.

function fib(n)
    if n = 0
        return 0
    else
        var prevFib = 0, currFib = 1
        repeat n − 1 times
            var newFib = prevFib + currFib
            prevFib = currFib
            currFib  = newFib
    return currentFib

---

Recursion vs Dynamic Programming 재귀 vs 동적 계획법

  동적 계획법은 거의 모든 재귀 알고리즘에 적용된다. 이것은 우연이 아니며 대부분의 최적화 문제는 재귀가 필요하며 최적화를 위해 동적 계획법이 사용된다.

 

  하지만 모든 재귀를 사용하는 문제가 동적 계획법을 사용하는 건 아니다. 피보나치 수열 문제처럼 겹치는 하위 문제가 존재하지 않는 한 재귀는 분할과 정복의 방식을 사용한 해답밖에 얻어낼 수 없다.

 

  이것이 병합 정렬(Merge Sort)같은 재귀 알고리즘에 동적 계획법을 사용할 수 없는 이유이다. 하위 문제들이 어떤 방식으로든 겹치지 않기 때문이다.

---

Greedy Algorithms vs Dynamic Programming 탐욕법 vs 동적 계획법

  탐욕법과 동적 계획법은 둘 모두 최적화를 위해 동작한다는 점에서 비슷하다.

 

  그러나, 탐욕법은 부분적으로 최적의 해답을 찾는다. 즉, 순간의 최적의 선택으로 전체의 최적의 결과를 찾아낸다. 그러므로 탐욕법은 부분적으로는 최적인 것처럼 보이지만 리스크가 크며 전체적으로 최적의 결과를 보장할 수 없다.

 

  그러나 동적 계획법에서는 하위 문제에 대한 최적의 솔루션을 찾은 다음 해당 하위 문제의 결과를 결합하여 최적의 솔루션을 찾기 위한 정보에 따른 선택을 합다.