Dynamic Programming

동적 계획법(Dynamic Programming) 알고리즘

---

동적 계획법은 Dynamic Programming의 줄임말로 DP로 불리기도 합니다.

동적 계획법은 주어진 문제를 작은 부분 문제로 나누어 푸는 알고리즘 설계 기법입니다.

동적 계획법과 분할 정복 알고리즘의 차이점은, 동적 계획법은 작은 부분 문제들은 서로 중복되는 문제가 존재하고, 이를 한 번만 계산하고 결과를 저장(Memoization)해 다시 사용하는 방식으로 빠르게 계산하는 것입니다.

동적 계획법은 크게 두가지 방식으로 할 수 있습니다.

1. Top-Down 방식 : 큰 문제를 작은 부분 문제들로 나누어 재귀적으로 해결하는 방식입니다.

2. Bottom-Up 방식 : 작은 부분 문제부터 시작하여 큰 문제를 해결해 나가는 방식입니다.

---

동적 계획법의 대표적인 예시는 피보나치 수열입니다.

피보나치 수열을 일반 재귀, Top-Down 방식, Bottom-Up 방식으로 구현하면 아래와 같습니다.

---

// 일반적인 재귀 알고리즘으로 구현한 코드입니다.
fun fibonacciRecursive(n: Int): Int {
    if (n <= 1) return n
    return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2)
}

이 코드는 일반적인 재귀 방식으로 계산하는 방식입니다.

단순하고 직관적이지만, 피보나치 수열의 계산 복잡도는 지수 시간 복잡도를 가지게 되어 큰 n값에서는 매우 비효율적입니다.

---

// Top-Down 방식의 동적 계획법 알고리즘으로 구현한 코드입니다.
fun fibonacciTopDown(n: Int, memoization: IntArray): Int {
    if (n <= 1) return n
    if (memoization[n] != 0) return memoization[n]

    memoization[n] = fibonacciTopDown(n - 1, memoization) + fibonacciTopDown(n - 2, memoization)
    return memoization[n]
}

이 코드는 Top-Down 방식을 사용한 동적 계획법으로 구현한 코드입니다.

큰 문제를 작은 부분 문제들로 나누어 재귀적으로 해결하고, memoization[n]이 0이 아닌 경우는 이미 계산되어 결과값이 저장되어 있는 경우이므로, 이 값을 그대로 반환함으로 중복 계산을 피합니다.

---

// Bottom-Up 방식의 동적 계획법 알고리즘으로 구현한 코드입니다.
fun fibonacciBottomUp(n: Int): Int {
    if (n <= 1) return n

    val memoization = IntArray(n + 1) { 0 }
    memoization[1] = 1

    for (i in 2..n) {
        memoization[i] = memoization[i - 1] + memoization[i - 2]
    }

    return memoization[n]
}

이 코드는 Bottom-Up 방식을 사용한 동적 계획법으로 구현한 코드입니다.

작은 부분 문제부터 시작하여 큰 문제를 해결하고, memoization 배열을 이용해 작은 문제부터 차례대로 계산하여 결과값을 저장하여 중복 계산을 피합니다.

---

위의 세 코드를 사용해 50번째 피보나치 수열의 값을 구할때의 실행 시간을 measureNanoTime을 사용해서 비교하면 아래와 같습니다.

• Top-down: 467530ns
• Bottom-up: 1620ns
• Recursive: 54738432900ns

동적 계획법으로 구현한 코드가 일반적인 재귀로 구현한 코드보다 훨씬 더 빠른 것을 알 수 있습니다.