동적 계획법을 사용하는 이유
동적 계획법은 부분 문제를 통해 큰 문제를 재귀적으로 해결하려고 할 때 중복되는 부분 문제들이 많이 발생하여 불필요하게 같은 계산이 반복될 때 사용된다. 이항 계수를 계산하는 공식은 아래와 같은 공식이 성립한다.
bino(n, r) = bino(n-1, r-1) + bino(n, r-1)
위 식에 대해 생각해보면 알 수 있듯이 주어진 n과 r에 대해 두 문제로 나눠가면서 계산했을 때 밑으로 내려가면서 중복되는 식이 점점 더 많이 발생함을 알 수 있다. n과 r의 크기가 커질 수록 중복되는 계산 역시 많아지는 데 그 양은 지수적으로 증가하기 때문에 큰 수에 대한 이항 계수는 단순한 재귀 호출로는 너무나 많은 시간이 든다
따라서 이 때 동적 계획법의 memoization을 이용하는 것인데, 그 방식은 그냥 매번 새로운 계산을 할 때마다 그 계산을 어떤 자료 구조에 기록해 놓는 것이다. 그러면 그리고 그 계산값이 필요할 때마다 배번 함수를 호출해 다시 계산하는 것이 아니라 그 자료를 참조해 바로 그 값을 얻는 방식이다. 이 방식을 사용하면 수십번, 수천번의 중복되는 계산도 한 번으로 줄일 수 있기 때문에, 계산양이 획기적으로 줄어든다.
메모이제션을 적용할 수 있는 경우
메모이제이션은 모든 중복 문제에 대해 적용되는 것이 아니다. 메모이제이션은 참조적 투명성이라는 특징을 가진 함수들에 대해서만 적용이 가능한데, 이 함수들의 특징은 입력에 대해서 항상 출력이 같다는 것이다. 간단히 생각해봐도 입력에 대한 출력이 상황에 따라 달라지는 함수들에 대해서는 기록한 값이 달라질 수 있기 때문에, 매번 계산을 다시 해주는 게 맞다는 것을 알 수 있다.
메모이제이션의 구현
메모이제이션은 알고리즘에서 매우 자주 사용하는 테크닉이므로, 그 구현을 일반화시켜 사용하는 것이 좋다. 일반적으로 메모이제이션을 위한 자료 구조로 n차원 배열을 사용하며, 배열의 값이 계산되지 않은 경우 -1로 초기화 해둔다. 배열의 값을 사용할 때 배열의 값에 대한 참조자를 선언하고 사용하여, 매번 어떤 인덱스를 쓸 지에 대한 고민을 줄일 수 있다.
