동적 계획법(Dynamic Progamming) - 알고리즘 문제해결 전략 공부 정리.

이 게시글은 알고리즘 문제 해결전략을 읽고 공부한 내용을 정리한 글입니다.

 

동적 계획법이란?

 

동적 계획법은 간단히 이야기해서, 완전 탐색법의 비효율성을 개선한 방법으로써, 중복되어 실행되는 부분의 중복을 제거하는 기법이다.

 

이때, 중복이 되는 부분은 전체 알고리즘의 부분 알고리즘인데, 이 부분적인 알고리즘이 수학적 함수의 성질을 가지고 있어야 한다. 수학적 함수의 성질이란 입력이 주어질 때, 외적인 변수는 함수의 출력에 영향을 주지 않고 오로지 입력만이 출력에 영향을 주는 함수를 뜻한다. (프로그래밍에서 함수는 전역변수 등으로 인해 이런 성질이 없는 경우가 많다.)

이런 수학적 함수의 성질을 가진 함수는 '참조적 투명성(referential transparency)'을 가졌다고 하고, '참조적 투명함수(referential transparent function)' 라고 한다. 

입력이 같으면 출력이 같다는 것은 그 함수를 중복해서 불러올 때에는 함수를 반복적으로 계산할 필요가 없다는 뜻이다. 함수에 출력이 정해지면, 그 출력을 미리 저장해두고, 한 번 계산된 입력에 대한 함수 출력은 계산없이 바로 출력만을 하면 된다. 이 과정을 메모이제이션이라고 한다. (Memoization)

메모이제이션의 패턴은 다음과 같다.

ret = [-1] * N # ret는 cache값으로써, 미리 전체에 -1을 저장해둔다고 가정하자.
# -1은 계산된 적이 없는 입력을 의미한다.

# 중략 ...

if ret != -1: # 해당 입력에 대한 출력이 존재하면 바로 출력한다.
	return ret

# 계산이 된 적이 없는 함수는 계산을 여기에서 한다.

return ret