08. 동적 계획법

08. 동적 계획법

8.1 도입

 

 동적 계획법과 분할 정복은 같은 접근 방식이라고도 볼 수 있습니다. 동적 계획법은 문제를 나누는 방식에서 차이가 납니다. 둘 다 부분 문제로 나누는 것은 같지만 동적 계획법에서의 부분 문제는 두 개 이상의 문제를 푸는데 사용될 수 있기에 cache 라는 곳에 부분 문제의 결과를 저장해두어 활용한다.

함수의 결과를 저장하는 장소를 마련해 두고, 한 번 계산한 값을 저장해 뒀다가 재활용하는 최적화 기법을 메모이제이션(memoization) 이라고 합니다. 메모이제이션은 함수의 반환 값이 그 입력 값만으로 결정되는 참조적 투명성 함수 에만 적용할 수 있다.

 

메모이제이션 구현 패턴

굉장히 자주 접하게 될 메모이제이션은 한 가지 패턴을 정해두고 항상 같은 형태로 구현 하면 버그를 찾기도, 작성하기 도 쉬워집니다.

1. 항상 기저 사례를 먼저 처리합니다. 입력이 범위를 벗어난 경우 등.

2. cache 를 초기화합니다. -1로 할지 numeric_limits 로 할지 등은 문제에 따라 정합니다.

3. ret 가 cache 의 참조형으로 사용된다. 고차원 배열에서의 인덱스 실수를 없애준다.

4. 메모이제이션용 배열을 초기화하는 방법을 알아두자. 정수형일 경우 memset 이 도움된다.

 

메모이제이션 시간 복잡도 분석

주먹구구식으로 이를 짐작해봅시다.

(존재하는 부분 문제의 수) x (한 부분 문제를 풀 때 필요한 반복문의 수행 횟수)

이러한 방식으로 수행 시간의 상한 을 짐작해 볼 수 있다.

 

동적 계획법 레시피 

1. 주어진 문제를 완전 탐색을 이용해 해결합니다.

2. 중복된 부분 문제를 한 번만 계산하도록 메모이제이션을 적용합니다.

외발 뛰기 JUMPGAME (레시피 적용해보기)

 

---

8.4 전통적 최적화 문제들

 

지금까지 어떤 경로로 이 부분 문제에 도달했건 남은 부분 문제는 항상 최적으로 풀어도 상관 없다. 라는 조건이 있다면 이것은 효율적인 동적 계획법 알고리즘을 적용하기 위해 아주 중요한 조건입니다. 최적 부분 구조(optimal substructure) 이라고 하며, 동적 계획법의 중요 요소 입니다.

 

최대 증가 부분 수열 (LIS) (boj 문제)

 

최대 증가 부분 수열 (LIS) (algospot 문제)

 

 

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

1. 모든 답을 만들어보고 최적해를 반환하는 완전 탐색 알고리즘을 설계
2. 전체 답의 점수를 반환하는 것이 아닌, 앞으로 남은 선택들에 해당하는 점수만을 반환하도록 부분 문제의 정의를 바꿈.
3. 재귀 호출의 입력에 이전의 선택에 관련된 정보는 꼭 필요한 것만 남기고 줄인다.
4. 입력이 배열이거나 문자열이라면 적절한 변환을 통해 메모이제이션 하도록 한다.
5. 메모이제이션 적용