[동적계획법] 0. 동적 계획법

종만북 8장 동적계획법. Dynamic programming

 

동적계획법vs분할정복법

 문제를 나누는 방식의 차이

 

 

동적계획법

- 점화식으로 표현 가능 → 두 번 이상 계산되는 `중복문제`를 알아낸다.

- `중복문제`를 해결하는 데 동적계획법 사용. 같은 문제를 또 계산할 필요 없잖아?

- 중복문제 계산값을 어디다 담아두느냐? `캐시(cache)`에.

  캐시에 저장해뒀다가 문제가 같으면 계산하지 않고 값만 꺼내 쓴다.

- 이렇게 결과를 저장해두었다가 재사용 하는 방법을 `메모이제이션(memoization)`이라고 부른다.

- 메모이제이션을 적용하려면 `참조적 투명성(referential transparency)`가 보장되어야 함

- 참조적 투명성이란? input이 같으면 같은 output이 나오는 것!

 

 

메모이제이션 구현 패턴

1. 기저 사례 처리; 조건이 안 맞으면 빨리 리턴시켜버리자

2. 캐시 초기화; 캐시를 -1로 초기화하자. 만약 계산값에 -1을 저장해야 한다면 다른 값으로 초기화하자.

3. &를 이용한다. C++기준으로 책이 쓰여 있어서 그런가. 편하긴 하다.

4. memset()이용. 캐시 초기화. memset(cache, -1, sizeof(cache)); //cstring, string.h에 있다.

 

 

메모이제이션의 시간 복잡도

= 존재하는 부분 문제의 수 X 한 문제 풀 때 필요한 반복문 수행 횟수

 

 

동적계획법 문제 해결법

1. 핵심 문제를 (재귀)함수로 표현. "무엇을 계산하고 무엇을 리턴하는 지" 나타낸다.

   * 재귀호출을 쓰지 않는 '반복적 동적 계획법'도 있다.

2. 해당 함수를 이용하여 점화식 생성.. 완전탐색으로 나올 수 있다.

3. 메모이제이션 적용