동적 계획법(dynamic programming)이란 말은 수학에서 유래한 용어이다. 의미를 살펴보면 프로그래밍 언어에서 말하는 동적(dynamic), 정적(static)이란 말과는 구별을 두어야 할 듯 싶다. 동적 계획법은 일종의 최적화 기법으로 어떤 문제를 부분적으로 나눌 수 있을 때 중복되는 문제해결 과정을 재사용하여 계산을 최적화 하는 기법이다. 이를 메모이제이션(memoization)이라고 한다.
예를 들어 어떤 문제집합을 풀 때 func(1,2)라는 호출이 여러번 있다면 func(1,2)라는 호출에 대한 결과를 캐시에 저장해 놓고 다음 호출 부터는 캐시에 있는 결과값을 바로 얻는 방식이다. 단 이 경우에 func(1, 2)라는 값은 언제나 동일함을 보장해야 한다.
가장 쉬운 예로는 피보나치 수열이 있다. 피보나치 수열은 점화식으로도 나타낼 수 있다.
점화식을 하나씩 풀어 써보면 an-4에 해당하는 항들이 여러개 생긴다. 물론 다른 항들 역시 중복되는 경우가 생기는데 n의 값이 커질수록 항들의 중복횟수는 더 많아진다. 파이썬으로 위 점화식(피보나치 수열)을 나타내면 다음과 같다.
n의 값을 적절히 조절해가면서 fibo(n)함수를 호출해 보자. 컴퓨터 cpu 성능에 따라 다르겠지만 적절한 지연(1~2초 정도)이 되는 n값이 있을 것이고 이 때부터는 n값을 조금만 올려도 지연 시간은 기하급수적으로 늘어날 수 있다. 대충 따져봐도 2^33 정도의 함수호출이 있게되기 때문이다. 사실 함수 호출 스택의 깊이는 33이 최대 깊이지만 깊이가 깊어질수록 재귀의 회귀와 함수의 호출이 기하급수적으로 반복된다. (2^32 = 약 42억)
그렇다면 이번에는 앞에서 설명한 동적 계획법을 사용해보자. 파이썬에서는 functools 모듈의 lru_cache 장식자를 사용하면 된다. 다음은 이를 사용하는 코드다.
결과는 같지만 속도는 획기적으로 빨라짐을 느낄 수 있을 것이다. n의 값을 100, 200으로 올리더라도 바로바로 결과가 계산된다. 사실 100으로 올리면 앞서의 방법으로는 계산이 불가능하다. 하노이의 탑처럼 말이다.
분석에 앞서 우선 다음 그림을 보자.
▲장식된 함수에서 cache_info 메소드를 호출 해서 실행된 함수가 어떻게 동작했는지에 대한 정보를 얻을 수 있다.
hits=33 은 캐시에 저장된 함수의 결과를 사용한 횟수를 말한다. misses는 캐시에 일치하는 경우가 없어서 함수가 실행된 경우다. 캐시의 사이즈는 128로 충분하므로 함수가 36번 호출되면서 결과가 모두 캐시에 저장된다. 따라서 currsize는 36이 된다. 이 중 hits한 경우는 33번 이므로 캐시에 저장되고도 사용되지 않은 경우는 3가지 뿐이다. (따져보면 아마 n, n-1, 0인 경우가 되겠다. 위 예에서는 35, 34, 0 인 경우.)
사실 총69번의 함수의 호출이 있었지만 만약 캐시를 사용하지 않는다면 앞서와 같이 80억번 이상의 함수호출이 있어야 한다. 이런 극심한 차이가 나는 이유는 다음 설명으로도 충분히 이해할 수 있다.
- 처음 그림에서 아래쪽 화살표 방향으로 먼저 함수가 호출된다.
- an-2가 계산되면서 결과가 캐시에 저장된다.
- 따라서 위쪽 화살표 방향으로의 함수호출은 실제로 이루어지지 않고 캐시에 저장된 an-2의 결과를 가져옴으로 해결된다.(이 것만으로도 전체 함수 호출 횟수가 반 정도가 준다.)
- 이런 식으로 줄다보면 총 69번의 함수호출만 생기게 된다.
생각해 볼 문제
피보나치 수열처럼 동적 계획법에 딱 들어맞는 알고리즘의 경우는 정말 획기적으로 계산의 성능이 좋아진다. 그러나 항상 딱 들어맞지 않는 경우에도 위 장식자를 사용할 필요도 있다. 예를 들어 특정 웹 사이트에서 뉴스기사를 매일 가져와서 읽을 경우를 생각해보자. 네트워크 상에서의 I/O는 상당시 지연시간이 많이 걸리는 작업이다. 이런 경우 사용자가 중복적으로 해당 사이트에 접속 했을 때 뉴스 기사가 바뀌지 않는 한 동일한 웹페이지를 전송해 줄 것이다. 앞에서 말한 동일한 호출과 동일한 결과에 부합된다. 이런 경우에도 위 장식자를 사용할 수 있다.
문제는 뉴스가 갱신되었을 때는 어떻게 하는가 하는 것이다. 앞서의 문제와 달리 동일한 호출이 조건(날짜, 시간, 기타 환경의 변화)에 따라서 결과가 달라질 수 있다는 것이다.
여러가지 해결방안이 있을 수 있겠지만 가장 간단한 방법으로는 저장할 캐시의 사이즈를 적절하게 조절하면 된다. 캐시가 작아지므로 오래된 기사의 경우는 캐시에서 사라지게 된다. 또는 주기적으로 캐시를 클리어 해주는 방법이 있다. lru_cache 장식자를 사용하면 장식을 받은 함수객체에 두 개의 메소드가 생기는데 하나는 앞에서 살펴본 cache_info고 하나는 캐시를 비우는 cache_clear 메소드다.
참고
위키백과-동적계획법