[알고리즘] 동적 프로그래밍(Dynamic Programming): 메모이제이션(Memoization), 테뷸레이션(Tabulation)

동적 프로그래밍(Dynamic Programming)

전에 분할 정복에 대해 다뤘던 적이 있

분할 정복은 큰 문제를 여러 개의 소문제로 나눠 해결해나가는 알고리즘이다.

이 작은 문제들을 매번 재계산하지 않고, 기억해두었다가 재사용하는 알고리즘이 동적 알고리즘이다.

 

동적 프로그래밍의 핵심은 소문제를 정의하는 것이다.

소문제를 정의하고, 이 소문제를 이용하여 다음 크기의 무제를 해결하는 방법을 제시할 수 있어야 한다.

또한 부분 문제들의 답이 중복되지 않게 최적의 방법으로 구해야 한다.

최적 부분 구조(Optimal Substructure)

어떤 문제가 최적 부분 구조로 이루어져 있을 때,

부분 문제들의 최적의 답을 구해 기존 문제의 최적의 답을 구할 수 있다.

 

동적 프로그래밍의 기본 기법으로는 메모이제이션(memoization)과 테뷸레이션(tabulation)이 있다.

메모이제이션(Memoization)

메모이제이션은 하향식(Top-Down) 방식이며, 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다.

즉, 재귀 호출에서 한 번 계산한 것을 기록하여 반복적으로 계산하지 않도록 하여 최적화하는 방법이다.

재귀 호출마다 계산한 값을 저장해야 하므로, 소문제 수만큼의 공간이 필요하다.

보통 다차원 배열을 이용하지만, 해시 맵을 사용하기도 한다.

 

메모이제이션의 대략적인 시간복잡도 계산법은 다음과 같다.

→ (존재하는 부분 문제의 수) * (한 문제를 풀 때 필요한 비용)

 

대부분의 블로그에서 피보나치를 예로 들고 있기 때문에, 나는 canSum 문제를 예시로 들겠다.

canSum이란 N개의 서로 다른 양의 정수가 있을 때, 원하는 만큼 합하여 목표 정수를 만들 수 있는지 알아내는 문제이다.

fun main() {
    val target = 7
    val arr = intArrayOf(5, 3, 4, 7)
    val memo = HashMap<Int, Boolean>()

    val isCan = memoization(target, arr, memo)
    
    if(isCan) println("YES")
    else println("NO")
}

fun memoization(target: Int, arr: IntArray, memo: HashMap<Int, Boolean>): Boolean {
    if(memo.containsKey(target)) return memo[target]!!
    if(target < 0) return false
    if(target == 0) return true

    for(i in arr) {
        val remainder = target - i
        if(memoization(remainder, arr, memo)) {
            memo[target] = true
            return true
        }
    }

    memo[target] = false
    return false
}

5, 3, 4, 7 중 3 + 4, 4 + 3, 7로 목표 정수인 7을 만들 수 있기에 "YES"가 출력된다.

재귀를 통해 한번 확인했던 값은 memo에 넣어서 기록해둔다.

즉, memo를 체크함으로써 어떤 주어진 입력값에 대해 계산을 해야하는지를 알 수 있고,

계산 결과를 memo에 저장하여 특정 값일 때의 결과값을 출력해주면 된다.

테뷸레이션(Tabulation)

메모이제이션이 하향식(Top-Down)이었다면, 테뷸레이션은 상향식(Bottom-Up)이다.

같은 시간복잡도를 가진다면 메모이제이션보다 테뷸레이션이 더 효과적인 방법이다.

단순히 반복문을 이용하여 밑에서부터 계산하는 방법하는 방법이라 생각하면 된다.

 

메모이제이션에서 예로 들었던 canSum을 테뷸레이션으로 구현해보자.

private const val target = 7
private val arr = intArrayOf(5, 3, 4, 7)

fun main() = with(System.`in`.bufferedReader()) {
    val check = tabulation()
    
    if(check) println("YES")
    else println("NO")
}

private fun tabulation(): Boolean {
    val table = BooleanArray(target + 1)
    table[0] = true

    for(i in 0 until target + 1) {
        if(table[i]) {
            for(j in arr) {
                if(i + j < target + 1) table[i+j] = true
            }
        }
    }

    return table[target]
}