동적 계획법(Dynamic Algorithm)(with. Kotlin)

동적 계획법은 정확하게는 알고리즘.. 이라는 느낌보다는 문제 해결 방법론에 가깝다.

동적 계획법은 같은 계산을 계속 반복하는 최적 부분 구조 알고리즘에 가장 편안한 방법이다. 동적 계획법의 경우 이전에 계산해둔 값을 저장해두고 다음 계산을 위해 재활용해서 사용하는 방식이기 때문이다.

 

동적 프로그래밍은 크게 상향식 접근의 타뷸레이션과 하향식 접근의 메모이제이션이 방법론으로 제기된다.

동적 계획법의 예시인 피보나치 수열을 타뷸레이션과 메모이제이션의 예시로 확인한다.

피보나치 수열을 동적 계획법을 사용해야하는 이유는 다음과 같다.

피보나치 수열은 다음과 같은 계산법을 가진다.

f(n) = f(n-1) + f(n-2)

 

 

이제 여기에 1 2 3 4... 순서대로 숫자를 넣어보자.

f(0) = 1
f(1) = 1
f(2) = f(1) + f(0) = 2
f(3) = f(2) + f(1) = (f(1) + f(0)) + f(1) = 3
f(4) = f(3) + f(2) = ((f(1) + f(0)) + f(1)) + (f(1) + f(0)) = 5
f(5) = f(4) + f(3) = (((f(1) + f(0)) + f(1)) + (f(1) + f(0))) + ((f(1) + f(0)) + f(1)) = 8

 

잘 보면

같은 값을 전역변수로 저장해서 쓰면 되잖아! <- 이 생각과

계산이 정말 기하급수적으로 늘어날 것 같은데? <- 이 생각이 동시에 들 것이다.

 

후자를 막기 위해 전자를 이용하는 방법이 동적 계획법이다(ㅋㅋㅋㅋㅋㅋ)

 

그럼 두 방법론을 살펴보자.

 

fun main(args: Array<String>) {
    
    // 32, 51, 72 번째의 피보나치 수열을 구한다.
    // 메모
    val memoArray = arrayOf(memo(32), memo(51), memo(72))
    val tabArray = tab(arrayOf(32, 51, 72))
}

// 메모이제이션
fun memo(number : Int) : Int{
    // 값을 저장하는 배열 = 
    val array = Array(number) {0}
    
    for(i in 0 .. number) {
        when(i) {
            0, 1 -> array[i] = 1
            else -> array[i] = array[i - 1] + array[i - 2]
        }
    }
    
    return array[number]
}

// 태뷸레이션
fun tab(list : Array<Int>) : Array<Int> {
    
    val array = Array(list.size) {0}
    val pib = Array(100) {1}
    
    for(i in 2 ..< pib.size) {
        pib[i] = pib[i - 1] + pib[i - 2]
    }
    
    for(j in 0 ..< list.count()) {
        array[j] = pib[j]
    }
    
    return array
}

 

1. 메모이제이션

메모이제이션은 하향식 접근 답게 바닥부터 시작하여 값을 가져온다.

극단적인 예시이긴 하지만, 메모이제이션은 계산을 먼저 해두지 않아 초기 메모리는 많이 먹지 않지만, 계산을 다시 해야하는 문제가 생길 수 있다.

 

2. 태뷸레이션

테뷸레이션은 상향식 접근답게 먼저 계산을 다 해두고 값을 가져온다.

처음 계산할 때 메모리를 많이 소모하지만 접근이 쉬워 추후 많은 양을 요구할 때 값을 가져오기 쉬워진다.