동적 계획법(Dynamic Programing)
동적 계획법은 최적화 문제를 연구하는 수학 이론에서 나왔다.
큰 의미에서 분할 정복과 같은 접근 방식을 가진다.
처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산한다.
계산한 답들로부터 원래 문제를 계산한다.
동적 계획법에서 어떤 문제는 두개 이상의 문제를 푸는데 사용될 수 있다. 그래서 여러 번 사용되는 답을 한번 계산 후 재활용하여 속도를 향상시킨다.
캐시(cache) - 이미 계산한 값을 저장해 두는 메모리의 장소.
Overlapping subproblems - 두 번 이상 계산되는 부분 문제.
메모제이션
함수의 결과를 저장하는 장소를 마련해두고, 한번 계산한 값을 저장해뒀다가 재활용하는 최적화 기법이다.
전에 계산된 값은 저장되어 재활용되기 때문에, 모든 부분 문제가 한번 씩만 호출된다고 보장할 수 있어, 함수 호출 횟수가 엄청나게 감소한다.
함수의 반환값이 그 입력값만으로 결정되는지의 여부를 참조적 투명성(referential transparency)라고 한다.
입력이 고정되어 있을때, 그 결과가 항상 같은 함수들을 참조적 투명 함수라 하고, 메모제이션은 참조적 투명함수의 경우에만 적용가능하다.
메모제이션 구현 패턴
동적 계획법은 가장 흔한 문제 유형 중 하나여서, 메모제이션을 굉장히 자주 구현한다.
한 가지 패턴을 가지고 구현하면, 작성하기도 버그 찾기도 쉬워진다.
- 항상 기저 사례를 먼저 처리한다.
- 입력이 벗어난 경우등을 기저 사례로 처리한다.
- 기저 사례 체크전 cache[]에 접근하면 오류가 발생할 수 있다.
메모제이션의 시간 복잡도 분석.
각 입력에 대해 함수를 처음으로 호출할 때와 다음으로 호출 할 때 걸리는 시간이 다르기 때문에 분석하는 게 약간 까다롭다.
메모제이션을 사용하는 알고리즘의 시간 복잡도를 굉장히 간단하게 계산할 수 있는 방법.
(존재하는 부분 문제의 수) x (한 부분 문제를 풀 때 필요한 반복문의 수행횟수).
문제 풀기
- 재귀호출에서 시작하기.
- 동적 계획 법 알고리즘을 만드는 첫단계는 해당문제를 재귀적으로 해결하는 완전 탐색 알고리즘을 만드는 것이다.
동적 계획법 레시피
- 주어진 문제를 완전 탐색을 이용해 해결.
- 중복된 부분 문제를 한번만 계산하도록 메모제이션 적용.
다른 구현 방법
재귀호출을 이용하지 않고, 동적 계획법 알고리즘 구현이 가능하다.
해당 방법을 재귀 호출이 아닌 for문을 사용하여, 반복적 동적계획법을 구현하는 것이다.
재귀 호출을 통해 구현하는 것이 메모제이션을 통한 접근에 좀 더 직관적이다.
전통적 최적화 문제들
동적 계획법의 가장 일반적인 사용처는 최적화 문제의 해결이다.
최적환 문제란 여러 개의 가능한 답중 가장 좋은 답을 찾아내는 문제이다.
최적화 문제를 동적 계획법으로 푸는 것 또한, 완전 탐색에서 시작한다.
최적화 문제 동적 계획법 레시피.
- 모든 답을 만들어 보고, 그 중 최적해의 점수를 반환하는 완전탐색 알고리즘을 설계한다.
- 전체 답의 점수를 반환하는 것이 아니라, 앞으로 남은 선택들에 해당하는 점수만을 반환하도록 부분 문제 정의를 바꾼다.
- 재귀 호출의 입력에 이전의 선택에 관련된 정보가 있다면, 꼭 필요한 것만 남기고 줄인다. 문제에 최적 부분 구조가 성립할 경우에는 이전 선택에 관련된 정보를 완전히 없앨 수도 있다. 여기서 우리의 목표는 가능한 한 중복되는 부분 문제를 많이 만드는 것.
입력의 종류 줄어들수록, 부분 문제 중복은 늘어나고 메모제이션도 최대한으로 활용가능 한다. - 입력이 배열이거나 문자열인 경우 가능하다면, 적절한 변환을 통해 메모제이션에 적용한다.
경우의 수 계산하기 레시피.
- 모든 답을 직접 만들어서, 세어보는 완전 탐색 알고리즘을 설계한다.
이때 경우의 수를 제대로 세기 위해서는 재귀 호출의 각 단계에서 고르는 각 선택지에 다음과 같은 속성 성립.
a) 모든 경우는 이 선택지들에 포하됨.
b) 어떤 경우도 두 개 이상의 선택지에 포함되지 않는다. - 최적화 문제를 해결할 때 처럼 이전 조각에서 결정한 요소들에 대한 입력을 없애거나 변형해서 줄인다. 재귀 함수는 앞으로 남아 있는 조각들을 고르는 경우의 수만 반환한다.
- 메모제이션을 적용.
DP문제 푸는 법 공통점.
완전탐색으로 풀기 -> 완전 탐색에서 겹치는 부분을 부분 문제를 찾기 -> 메모제이션 적용.
REFERENCE
프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략 - 구종만
