Page 4 -

5장 설계 기법(3): 동적 계획법 095

5.1 동적 계획법이란? 096
5.2 동적 계획법 예제 097
5.3 동적 계획법 관련 개념도 102
5.3.1 완화 102
5.3.2 끌기 전이 형식과 밀기 전이 형식 105
5.3.3 끌기 전이 형식과 밀기 전이 형식 비교 107
5.3.4 전체 탐색 메모이제이션을 이용한 동적 계획법 107
5.4 동적 계획법 예제(1): 냅색 문제 110

5.5 동적 계획법 예제(2): 편집 거리 114
5.6 동적 계획법 예제(3): 구간 분할 최적화 119
5.7 정리 123

5.8 연습 문제 124

6장 설계 기법(4): 이진 탐색법 127

6.1 배열 이진 탐색 128
6.1.1 배열 이진 탐색 128
6.1.2 배열 이진 탐색 복잡도(*) 131
6.2 C++의 std::lower_bound() 132

6.3 일반화한 이진 탐색법 133
6.4 좀 더 일반화한 이진 탐색법(*) 135

6.5 응용 예(1): 나이 맞히기 게임 136
6.6 응용 예(2): std::lower_bound() 활용 138
6.7 응용 예(3): 최적화 문제를 판정 문제로 바꾸기 140
6.8 응용 예(4): 중앙값 구하기 143

6.9 정리 143
6.10 연습 문제 144

020