한빛출판네트워크

이 글은 다이내믹 프로그래밍Dynamic Programming에 대해 들어봤거나 들어보진 못했지만 알아보고 싶은 사람들을 위함이다. 여기서는 다이내믹 프로그래밍과 일을 할 때 도움이 될만한 모든 주제를 다뤘다.

 

차례:

다이내믹 프로그래밍 소개

꼭 필요한 다이내믹 프로그래밍의 성질

다이내믹 프로그래밍 사용

다이내믹 프로그래밍 문제 해결하는 접근 방식

적용 사례

 

 

다이내믹 프로그래밍 소개

다이내믹 프로그래밍이 다이내믹 기억 장치 스페이스dynamic memory space와 관련이 있다고 생각한다면 오산이다. 다이내믹 기억 장치와 관련이 없다.

 

이제 질문을 던져보자. 그렇다면 다이내믹 프로그래밍이란 무엇인가? 간단하게 설명하자면, 다이내믹 프로그래밍은 최적화된 재귀recursion로, 다항 시간polynomial time(재귀가 그렇듯 지수적은 아님)에 문제를 해결하는 것이다.

 

그렇다. 다이내믹 프로그래밍은 재귀에 대한 최적화일 뿐이다. 다이내믹 프로그래밍은 사실 중복된 (곧 해결될)부분 문제subproblem가 있다면 이에 대한 결과를 저장하고 동일한 부분 문제가 다시 발생한다면, 이 결과를 재사용하는 것이다. 이 아이디어로 시간과 비교 횟수를 절약해준다.

 

재귀를 잘 모르는 이들을 위해서 간략하게 설명하자면, 재귀란 문제를 해결하는 방법으로 큰 문제를 작은 부분 문제로 나눈 다음, 부분 문제의 결과를 사용하여 큰 문제를 해결하는 데에 사용하는 것이다.

 

이제부터 어떻게 다이내믹 프로그래밍이 재귀로 최적화optimization를 했는 지 알아보려고 한다.

 

 

꼭 필요한 다이내믹 프로그래밍의 성질

다이내믹 프로그래밍이 재귀로 어떻게 최적화를 했는 지 알아보기 전에 먼저 다이내믹 프로그래밍으로 어떤 문제를 해결할 수 있는지 알아봐야 한다.

 

1. 부분 문제와 중복되는 문제들

알다시피 재귀에서는 문제를 부분 문제로 나눈다. 여기서 계속해서 연산해야 하는 몇 가지 부분 문제가 존재한다면 그것이 바로 중복된 부분 문제overlapping subproblem인 것이다. 다이내믹 프로그래밍에서는 부분 문제의 결과를 저장하고(방법은 밑에 설명), 필요할 때마다 다시 연산하는 것이 아니라 이전의 결과를 사용한다. 이러한 방법으로 프로그래머들의 피같은 시간을 아낄 수 있다.

 

피보나치 수열에서 n번째 항을 찾는다고 해보자. 5번째 항을 구하려면 3번째 항을 두 번, 2번째 항을 세 번 연산해야 한다. 그림으로 보면 다음과 같을 것이다.

 

공통된(중복된) 부분 문제가 없는 문제는 문제 해결값을 다시 쓸 일이 없기 때문에 저장할 필요도 없어지므로 이러한 경우 다이내믹 프로그래밍은 도움이 안된다.

 

재귀가 많은 분할 정복Divide and Conquer 알고리즘에서 사용되지만 위 알고리즘의 경우 부분 문제가 중복되지 않기 때문에 다이내믹 프로그래밍을 사용할 수 없는 것이다.

 

2. 최적 부분 구조optimal substructure

최적 솔루션을 해당 부분 문제의 최적 솔루션으로 계산할 수 있다면 최적 부분 구조가 있을 것이다.

 

피보나치 수열과 유사하게 최적 부분 구조는 fib(n) = fib(n-1) + fib(n-2) 이다. 피보나치 수열에서 (n-1)번째 항과 (n-2)번째 항으로 n번째 항을 계산하는 것과 같이 말이다.

 

어떠한 문제든 이 두 가지 성질을 찾는다면 그 문제는 다이내믹 프로그래밍으로 해결할 수 있다.

 

 

다이내믹 프로그래밍 구현

여기서 다이내믹 프로그래밍이 재귀로 어떻게 최적화했는지 알아보자.

 

1. 하향식 접근 Top-down approach

하향식 접근 방식은 재귀에 일부 수정만 했을 뿐 매우 유사하다. 여기서 부분 문제에 대한 결과를 메모 배열memo array에 저장한다(다른 구조를 사용해도 된다). 나중에 다시 필요할 때 메모 배열에서 결과값을 찾을 수 있기 때문이다.

 

n번째 피보나치 수열 문제의 하향식 접근은 다음과 같이 해볼 수 있다.

 

 

/*

    c++

 

    optimization of fibonacci numbers implementation

    time comlexity : O(n) rather than exponential ,as in older recursive implementation.

*/

int fib(int n, int memo[])

{

    if (memo[n] == -1) // if we encounter this number first number, as memo[] is initialized with -1

    {

        int res;

        if (n == 0 || n == 1)

        {

            res = n;

        }

        else

        {

            res = fib(n - 1, memo) + fib(n - 2, memo);

        }

        memo[n] = res;

    }

    return memo[n];

}

 

 

하향식 접근으로 5번째와 3번째 항은 1번만 연산하면 되며 다음 항부터 메모 배열에서 결과값을 가져올 것이다. 2번째도 마찬가지다.

 

핵심 문제(재귀 중 윗 단계)에서부터 시작하고 부분 문제로 나누며 부분 문제의 결과를 보관하기에 이러한 접근 방식은 하향식 접근, “Top-Down Approach”라고 불린다. 또한 메모이제이션Memoization이라고 불리기도 한다.

 

2. 상향식 접근 Bottom-up approach

상향식 접근 방식은 위의 하향식 접근과 정반대이기에 재귀를 사용하지 않는다. 상향식 접근은 부분 문제를 먼저 해결(상향식)하고 table에 결과를 저장한다. 그리고 윗 단계 문제를 이 table 결과값을 사용해 연산해나가는 것이다.

 

n번째 피보나치 수열 문제의 상향식 접근은 다음과 같이 해볼 수 있다.

 

 

// c++

int fib(int n)

{

    int table[n + 1];

    table[0] = 0, table[1] = 1;

    for (int i = 2; i <= n; i++)

        table[i] = table[i - 1] + table[i - 2];

    return table[n];

}

 

1차원 배열을 사용한 이유는 무엇일까? 배열 차원은 재귀 구현 시 바뀌는 변수의 수에 따라 정해진다. n번째 피보나치 항의 재귀 구현을 안다면 한 번 재귀적 호출에 하나의 매개 변수씩만 바꿀 수 있다는 것을 이해할 수 있을 것이다. 그래서 바로 1차원 배열만 사용한 것이다.

 

이러한 접근을 Tabulation이라고 한다.

 

이렇게 다이내믹 프로그래밍은 문제별로 구현하는 접근을 바꿔가며 재귀로 최적화를 한다.

 

 

다이내믹 프로그래밍 문제 해결 접근 방식

이제 두번째 단계다. 이제 다이내믹 프로그래밍 문제를 해결하기 위해 우리가 어떻게 접근해야 하는지에 대해 얘기해보자.

 

무차별 대입 방식보다 다이내믹 프로그래밍 솔루션이 더 빠르기 때문에 문제 해결할 때 다이내믹하게(동적으로) 생각해야한다.

 

1. 다이내믹 프로그래밍임을 식별: 첫번째로 주어진 문제가 다이내믹 프로그래밍으로 해결될 수 있는 지 식별한다. 식별하는 방법은 위에서 “꼭 필요한 다이내믹 프로그래밍의 성질”을 찾아내는 것이다.
2. 매개 변수를 결정: 두번째로 궁극적으로 문제 해결을 하기 위해 어떤 것이 매개 변수가 될 지 결정을 한다. 피보나치 수열의 경우 n이다.
3. 매개 변수를 부분 문제와 연결: 이제 두번째 단계에서 결정해놓은 매개 변수를 다른 문제와 연결 짓는다. 7번째 피보나치 항의 경우 n=7이므로 이는 fib(n=7) = fib(n=6) + fib(n=5)로 정리할 수 있다. 한마디로 최적화된 부분 구조를 설계하는 것이다.
4. 문제 코딩: 마지막 단계로 문제에 대해 코드를 작성한다. 상향식, 하향식 접근 중 한 가지를 택해서 말이다.

 

이게 바로 다이내믹 프로그래밍 문제를 해결하는 간단한 4단계이다.

 

 

적용

컴퓨터 사이언스 관점으로 봤을 때 다이내믹 프로그래밍을 기반으로 한 많은 문제가 존재하기에 다이내믹 프로그래밍을 적용할 곳이 많다. 그 중 몇 가지를 소개 해보자면 다음과 같다.

 

• Diff Utility (Longest Common Subsequence 문제 기반): 두 개의 파일의 차이점을 알아내기 위해 쓰인다. Git에서도 사용된다.
• Resource Allocation(0-1 배낭knapsack 문제 기반)
• ️연관 검색어 검색 (Edit distance 문제 기반)
• 플로이드-워셜 알고리즘Floyd-Warshall Algorithm: 그래프의 모든 정점의 쌍의 최단 거리를 찾아내는 알고리즘.
• 벨만-포드 알고리즘Bellman-Ford Algorithm: source router와 destination router 사이 최단 거리를 찾아내는 알고리즘.

 

 

*****

원문: What is Dynamic Programming   Originally published on Hacker Noon

번역: 김정욱