[Algorithmic Problem Solving Strategies] 8. 동적계획법

알고리즘 문제 해결 전략 세트 국내도서 저자 : 구종만 출판 : 인사이트 2012.11.23 상세보기

알고리즘 문제 해결 전략 세트구종만 상세보기

 

8.1 도입

==========
- 메모제이션: 함수의 결과를 저장하는 장소를 마련해 두고, 한 번 계산한 값을 저장해 뒀다 재활용하는 최적화 기법 = 참조적투명함수의 경우에만 적용

- 참조적 투명성: 함수의 반환값이 그 입력값만으로 결정되는지 여부 = 입력이 고정되어 있을 때, 그 결과가 항상 같을 경우

- 동적계획법: 두 번 이상 반복 계산되는 부분 문제들의 답을 미리 저장함으로써 속도의 향상을 꾀하는 알고리즘 설계기법

- 메모이제이션 패턴: 항상 기저사례를 제일 먼저 처리
​​​​​​// 전부 -1로 초기화
int cache[2500][2500];

// a와 b는 각각 [0, 2500) 구간 안의 정수
// 반환 값은 항상 int형 안에 들어가는 음이 아닌 정수
int someObscuresFuntion(int a, int b){
// 기저 사례를 처음에 처리
if( ... ) return ...;

// (a, b)에 대한 답을 구한 적 있으면 곧장 반환
int& ret = cache[a][b];
if(ret != -1) return ret;

// 여기서 답을 계산 (후 캐시 저장)
...
return ret;
}

int main(){
// memset()을 이용해 cache배열 초기화
// 쉽게 초기화 하는 방법 알아두기
memset(cache, -1, sizeof(cache));
}

- 메모제이션의 시간 복잡도 분석
(존재하는 부분 문제의 수) X (한 부분 문제를 풀 때 필요한 반복문의 수행 횟수)

- 풀이방법

재귀 호출에서 시작하기: 완전 탐색 알고리즘 만들기
중복된 부분 문제를 한 번만 계산하도록 메모제이션을 적용

재귀호출을 이용하지 않고 동적 계획법 알고리즘 구현 할 수도 O = 반복적 동적 계획법

- 동적계획법 레시피

1. 주어진 문제를 완전 탐색을 이용해 해결
2. 중복된 부분 문제를 한 번만 계산하도록 메모제이션 적용

8.2 와일드 카드 문제

=========

8.4

=========
- 최적화 문제 동적 계획법 레시피

1. 완전 탐색 알고리즘 설계: 모든 답을 만들어 보고 그 중 최적해의 점수를 반환하는
2. 앞으로 남은 선택들에 해당하는 점수만을 반환하도록 부분 문제 정의를 바꿈(전체 답의 점수 반환 X)
3. 가능한 한 중복되는 부분문제를 많이 만드는 것! = 입력의 종류가 줄어들수록 더 많은 부분 문제가 중복 = 메모제이션을 최대로 활용!
   (1) 재귀 호출의 입력에 이전의 선택에 관련된 정보가 있다면 -> 꼭 필요한 것만 남기고 줄인다.
   (2) 문제에 <최적 부분 구조>가 성립할 경우 -> 이전 선택에 관련된 정보를 완전히 없앰
4. 입력이 배열이거나 문자열인 경우) 가능하다면 적절한 변환을 통해 메모제이션 할 수 있도록 함
5. 메모제이션 적용