[Algorithm] Dynamic Programming (동적 계획법)

dEpayse

Published in

dEpayse_publication

8 min readMar 19, 2023

이번 포스트에서는 Dynamic Programming (동적 계획법)에 대해 알아보려고 한다.

Dynamic Programming 이란?

Dynamic Programming 은 알고리즘 설계 기법 혹은 패러다임 중 하나이다.

Dynamic Programming 은 어떤 문제가 중복되는 여러 하위 문제로 나누어지고, 하위 문제들의 최적해를 결합하면 결국 상위 문제의 최적해와 같은 경우, 중복된 문제를 매번 계산하는 것이 아닌 한 번만 계산하고 저장한 후 가져오는 방법으로 문제를 해결하는 최적화된 방법이다. 이와 같은 경우를 짧게 overlapping subproblems(중복되는 하위 문제들), optimal substructure(최적 부분 구조) 라고 한다.

overlapping subproblems(중복되는 하위 문제) : subproblem 이 중복되는 경우가 여러 번 발생하는 경우이다. 그렇기에 이것을 매번 계산하지 않고 처음 한 번만 계산하여 계산한 값을 배열이나 해시 테이블에 저장해두었다가 다음 번 수행 시 값을 가져오기만 한다.
optimal substructure(최적 부분 구조) : 주어진 문제에 대한 최적해를 구하고자 할 때, 좀 더 작은 sub-problem들에 대한 optimal solution들을 찾은 후 그것들을 결합하면 결국 전체 문제의 optimal solution 이 되는 경우이어야 한다.

사실 Dynamic Programming(동적 계획법)은 이름이 그 의미를 잘 나타내지는 않다고 생각하고, 그런 의견이 많다. 미국의 수학자인 Richard Bellman 이 고안해낸 이 패러다임은 이름 지을 때 마음대로 이름을 지을 수 없는 상황이었다는 이야기도 있고, 펀딩을 위해 그럴싸한 이름이 필요해서 지어졌다는 이야기도 있다. 무엇이 진짜인지는 모르겠지만, 역시 이름이 그 의미를 잘 나타내진 못하는 것 같다.

동적 계획법 접근법

동적 계획법의 접근법에는 큰 문제부터 시작하여 작은 문제를 해결한 후 결국엔 원하는 답을 얻는 Top-down 방식과, 작은 문제부터 시작하여 원하는 답을 얻는 Bottom-up 방식이 있다. 서로의 단점은 반대되는 것의 장점이 되기때문에 상황에 맞게 접근하면 될 것 같다.

Top-down 방식 — 더 큰 문제를 해결하는 함수부터 호출하고, 큰 문제 내부에서 작은 문제를 해결하는 함수를 호출하여 큰 문제의 원하는 값을 얻는 방식이다. 큰 문제에서 작은 문제를 해결해야하기 때문에 재귀적으로 함수를 호출하고, 따라서 함수 호출 depth 가 많아질 수 있고 stack overflow 가 발생할 가능성 역시 배제할 수 없다. 함수 외부에서 수열의 값을 저장하는 Memoization 기법을 이용한다. (Memo 해가며 해결한다하여 Memoization 이다. Memorization 과는 구분된다.)
Bottom-up 방식 — 작은 문제부터 해결하여 수열의 구하고자 하는 큰 문제까지 모두 iteration 하여 큰 문제를 해결하는 방식이다. Tabulation(표) 기법이라고도 한다. Memoization 과 다르게 Iteration 하며 계산하기 때문에, 필요없는 연산이 수행될 수도 있다. 그러나 재귀적으로 호출하지 않기 때문에 함수 스택이 부족할 걱정은 없다.

Dynamic Programming 적용 예시 — Fibonacci sequence

이 파트는 Dynamic Programming 을 보여줄 수 있는 예시이다. 이 예시가 아니더라도 문제가 overlapping subproblems 로 나누어질 수 있고, optimal substructure 를 갖는다면 Dynamic Programming 을 활용하여 해결할 수 있다.

n 번째 수열의 값을 그 전의 항들로 표현하는 ‘점화식(Recurrence relation)’ 으로 수열을 표현할 수 있다면, Dynamic Programming 을 이용하여 최적화 할 수 있는 경우가 많다. 피보나치 수열도 그 중 하나이고, 피보나치 수열의 정의는 다음과 같다.

즉 피보나치 수열은 0, 1, 1, 2, 3, 5, 8, 13, … 으로 나타난다. 피보나치 수열의 특정 값을 구하는 프로그램을 작성해보자.

만약 Dynamic Programming 을 사용하지 않고 값을 구하는 함수를 작성한다면, Ex1–1 과 같이 구할 수 있다. (편의상 Int 로 구현하여, Int 의 범위를 넘어서는 피보나치 결과값은 정상적으로 계산될 수 없음에 유의하자.)

// Ex1-1. Dynamic Programming 을 사용하지 않고 단순 재귀로 구하기
fun fibonacciRecursive(n: Int): Int =
    when {
        n <= 0 -> 0
        n == 1 -> 1
        else -> fibonacciRecursive(n-2) + fibonacciRecursive(n-1)
    }

그러나 Ex1–1 과 같은 방식으로 구현하면 연산 시간이 오래 걸리거나, stack overflow 가 발생할 수 있다. 그 이유에 대해 알아보기 위해 아래 Fig5 를 보자.

**Fig1–1**. Fibonacci(5) 값을 구하기 위해 Ex1–1 의 함수가 쳐야 하는 과정

Fig1–1 은 Fibonacci(5)를 구하기 위해 단순 재귀 함수로 구현한 Ex1–1 의 함수가 거쳐야 하는 과정을 나타낸 것이다(‘Fibonacci’ 는 간단하게 ‘F’ 로 나타냈다.). F(5)를 구하기 위해 F(3)과 F(4)를 계산해야 하는데, F(4)를 계산하기 위해 F(3)을 구하는 과정을 반복해야 한다. F(3)의 하위 과정인 F(2)가 중복되는 횟수는 F(3)보다 더 많다.

0번째부터 시작하여 여섯 번째의 피보나치 값을 구하는 것인데, 연산 수는 F(5)의 경우 함수 호출이 총 15 번이나 되고, 함수 호출 스택도 depth 가 3 이 넘는 것을 볼 수 있다. n 이 커질 때, 연산 수는 급수적으로 증가하는 것을 예상할 수 있다. 함수 호출 스택 크기 역시 n 과 비례하는 것을 예상할 수 있다.

그럼 위와 같이 Fibonacci 수열의 값을 구하는 것을 봤을 때, 다음과 같은 특징을 갖는 것을 생각해볼 수 있다.

optimal substructure => F(2) = F(0) + F(1) 이고, F(3) = F(1) + F(2) 이다. 즉 더 작은 입력값의 피보나치 수열 값들을 더하여 큰 입력값의 결과값을 얻을 수 있다.
overlapping subproblems => F(2) = F(0) + F(1) 이고, F(3) = F(1) + F(2) = F(1) + F(0) + F(1) 에서, F(2) 를 보면 알 수 있듯 하위 문제들이 중복된다.

따라서 Ex1-2 와 같이 Fibonacci 수열을 구할 때 Dynamic Programming 을 사용하여 더 효율적으로 값을 구할 수 있다.

// Ex1-2. Dynamic Programming(Bottom-up 방식인 Tabulation)을 사용하여 값 구하기
fun fibonacciDP(n: Int): Int {
    // 한 번 계산한 후 저장하고 값을 참조하여 사용하기 위한 배열
    val fibonacciSequence = IntArray(n + 1).apply {
        set(0, 0)
        set(1, 1)
    }
    // 이후 n 까지 차례대로 계산
    (2..n).forEach {
        fibonacciSequence[it] = fibonacciSequence[it-2] + fibonacciSequence[it-1]
    }
    return fibonacciSequence[n]
}

**Fig1–2**. Fibonacci(5) 를 Dynamic Programming 을 활용하여 구하는 과정

두 과정의 연산의 시간 복잡도를 비교해보면 단순 재귀는 O(2^N)이 되지만, Dynamic Programming 을 사용하여 최적화하면 O(N)이 된다. 만약 Ex1–2 에서 Tabulation 방식이 아닌 Top-down 방식으로 진행한다면, 시간 복잡도는 O(N)이겠지만 함수 호출 스택의 Depth 는 단순 재귀와 같아지기 때문에 Bottom-up(Tabulation) 으로 작성했다.

Dynamic Programming 이 사용되는 알고리즘

Dynamic Programming 은 Dijkstra(데이크스트라) 알고리즘, Bellman-Ford(벨만-포드) 알고리즘 등 다른 알고리즘에서도 사용된다. 해당 알고리즘들에 대해서는 본 포스트에서 다루지 않는다.

Reference

[CPUU의 Daydreamin’] “Dynamic Programming” — https://cpuu.postype.com/post/3698892
[Wikipedia] “Dynamic Programming” — https://en.wikipedia.org/wiki/Dynamic_programming
[나무위키] “동적 계획법” — https://namu.wiki/w/%EB%8F%99%EC%A0%81%20%EA%B3%84%ED%9A%8D%EB%B2%95