Dynamic Programming에 대하여

Dynamic Programming(이하 동적계획법)은 Divide and Conquer(이하 분할정복법)와 같이

문제를 작은 문제들로 나누어 연산을 반복해 최종 해답을 얻는 방식이다.

 

하지만 분할정복법과 다른 부분은 바로 Memoization을 사용한다는 것이다.

즉, 분할정복법에서는 작게 나눈 문제가 중복될 경우 낭비가 발생하지만 동적계획법은

값을 저장함으로서 중복된 문제를 풀때의 낭비가 없도록 한다.

 

대표적인 예시로는 피보나치 수열이 있겠다.

fun fibo(n): Long {
    if(n == 1) return 1
    else if(n == 2) return 1
    else return fibo(n-1) + fibo(n-2)
}

 

아주 대표적인 피보나치 수열의 값을 얻는 함수이다.

 

위처럼 작성하면 굉장히 간단하게 값을 얻을 수 있지만

n의 값이 조금만 커지게 되어도 콜스택을 어마어마하게 잡아 먹을 것이다.

 

그리고 어느 정도 n이 커지면 stackoverflow를 만나게 될 것이다.

 

위와 같은 문제를 memoization을 통해 해결할 수 있다.

값을 배열에 저장하는 간단한 방법 말이다.

val fiboValueList = mutableListOf<Long>(0, 1, 1)
fun fibo(n: Int): Long {
    if(n == 1) return 1
    else if(n == 2) return 1
    else {
    	for(i in 3..n) {
            fiboValueList.add(fiboValueList[i-1] + fiboValueList[i-2])
        }
        return fiboValueList[n]
    }
}

 

배열에 다음 값을 저장하면서 propagation하는 모습이다.