동적 계획법(Dynamic Programming) 알아보기

똑같은 계산을 계속 반복해야 하는 알고리즘에서
계산 값을 저장해 둬서 반복하지 않게 하는 방법

 

• 동적 계획법이라는 이름은 아마 정적으로 계획없이 똑같은 계산을 반복하는게 아니라 동적(적극적)으로 계획해서 계산을 줄이는 방법이라 그렇지 않을까 개인적으로 추측해 봅니다.
• 동적 계획법을 쓰던 안 쓰던, 정확성은 Brute-Force와 차이가 없습니다. 하지만, 훨씬 더 효율적입니다.

---

예시 : 피보나치 수열 구하기

피보나치 수열은 1, 1 부터 시작해서 그 전 2개의 항을 더한게 n번째 항인 수열입니다.

이 정의를 그대로 코드로 구현하면 아래와 같습니다.

fun fibo(n: Int): Int {
    if (n <= 2) return 1
    
    return fibo(n - 1) + fibo(n - 2)
}

 

언뜻 보면 아무 문제도 없어 보이지만, 이 코드에서 한 계산을 트리로 나타내 보면 반복이 많은걸 알 수 있습니다.

그래서 같은 계산을 하지 않기 위해 처음 계산하면 메모 해 두고, 같은 계산이 나오면 그 메모를 참고하는 식으로 코드를 바꿔보면 아래와 같이 훨씬 더 효율적인 알고리즘이 됩니다. (다만 코드는 더 복잡해 집니다)

fun fibo(n: Int, memo: IntArray): Int {
    if (memo[n] != 0) return memo[n]
    if (n <= 2) return 1
    
    memo[n] = fibo(n - 1, memo) + fib(n - 2, memo)
    return memo[n]
}

 

위 코드를 트리로 나타내면 훨씬 간단한걸 알 수 있습니다.

---

메모이제이션(Memoization)? 타뷸레이션(Tabulation)?

동적 계획법에는 2가지 방법이 있습니다. 메모이제이션과 타뷸레이션입니다.

 

위에서 보여드린 방법이 메모이제이션입니다. 메모이제이션은,

• 일반적으로 재귀(recursion)으로 구성됨
• 위에서 시작해서 아래로 가는 방식 (Top-down)

이와는 반대로 타뷸레이션은,

• 재귀를 쓰지 않고 반복문을 쓰는 경우가 많음
• 아래에서 시작해 위로 올라가는 방식 (Bottom-Up)

 

같은 피보나치 수열을 파뷸레이션으로 풀이하면 아래의 코드처럼 반복문을 쓰게 되고, 아래에서 위로 올라가는 방식입니다.

fun fibo(n: Int): Int {
    val tab = IntArray(n + 1)
    tab[0] = 0
    tab[1] = 1
    
    for (i in 2..n) tab[i] = tab[i - 1] + tab[i - 2]
    
    return tab[n]
}

---

우리는 이미 메모화(Memoization)을 쓰고 있다

메모화는 이미 한 계산을 메모해 둬서 같은 계산을 반복하지 않아 훨씬 효율적으로 답을 구하는 방법니다. 워낙에 상식적인 방법이라 일상생활에서도 우리는 메모화를 자주 쓰고 있습니다.

바로 구구단이 메모화이기 때문입니다!

생각해 보시면, 구구단은 곱셈의 결과를 메모한 계산표를 외워서 계산을 빠르게 하는 방법이니, 메모화의 정의와 맞습니다.

---