빠르고 우아한 상향식 문제 풀이법으로 코딩 면접 광탈에서 멘탈갑으로 거듭나기 다이내믹 프로그래밍(동적 계획법)은 알고리즘을 공부하다 마주치는 첫 번째 큰 장벽이다. 이 책은 알고리즘 공부의 걸림돌을 디딤돌로 만들기 위해 다이내믹 프로그래밍이라는 한 가지 주제만을 철저히 파고든다. 재귀 호출, 메모 전략, 상향식 다이내믹 프로그래밍의 개념을 자세히 설명하고, 고전 알고리즘 문제부터 단골 인터뷰 문제까지 다양한 예제에 세 가지 방법을 적용해본다. 늘 헷갈리던 개념을 확실히 이해하고, 문제 풀이에 적용할 수 있게 될 것이다.
코딩 인터뷰 전문 스타트업 리탐바라 테크놀로지(www.ritambhara.in)의 공동설립자. 컴퓨터사이언스 석사 학위가 있으며 기술 스타트업 창업가, 공인 요가 트레이너, 두 아이의 엄마 등 역할이 많지만 워라밸을 잘 유지하고 있다. 말하자면 삶 속에서 문제 풀이와 최적화를 실천하고 있다.
[PART 1 재귀 호출의 모든 것]CHAPTER 01 재귀 호출의 이해1.1 재귀 접근 방법이란?__예제: 1에서 n까지 양의 정수의 합을 계산하기__예제: 점화식으로 제곱 계산하기__예제: 하노이의 탑__선행 재귀와 후행 재귀__재귀를 사용한 문제 해결1.2 재귀 호출과 메모리 __프로세스 주소 공간__재귀 호출을 사용할 때와 사용하지 않을 때의 메모리 상태 비교__메모리 배치를 알면 문제 풀이에 도움이 됩니다__마치며CHAPTER 02 재귀 호출의 특징과 메모 전략2.1 최적의 하위 구조__다이내믹 프로그래밍에서 최적의 하위 구조 활용하기2.2 하위 문제의 반복 계산__예제: 피보나치 수열__예제: 역 사이 최소 비용 구하기2.3 메모 전략[PART 2 드디어 다이내믹 프로그래밍]CHAPTER 03 다이내믹 프로그래밍의 이해3.1 다이내믹 프로그래밍이란?__예제: 부분 문자열 다루기3.2 하향식 접근 방법과 상향식 접근 방법__예제: 계승 함수__예제: 이진 트리__상향식 다이내믹 프로그래밍이 좋지 않은 경우CHAPTER 04 다이내믹 프로그래밍 적용 전략4.1 세 방법을 차례대로 적용하며 문제 풀기__예제: 행렬에서 최소 이동 비용 구하기4.2 다이내믹 프로그래밍을 사용한 문제 해결__다이내믹 프로그래밍을 적용할 수 있을까요?__다이내믹 프로그래밍으로 문제 풀기__예제: 타일로 공터 채우기__예제: 특정 점수에 도달하는 경우의 수 구하기__예제: 연속된 부분 배열의 최댓값 구하기[PART 3 지금부터 게임을 시작하지]CHAPTER 05 실전 문제5.1 최소 교정 비용 문제5.2 직사각형에서 총 경로 수 구하기5.3 문자열 인터리빙 확인 문제5.4 부분집합의 합 구하기5.5 최장 공통 부분 수열 길이 구하기5.6 최장 공통 부분 수열 출력하기5.7 거스름돈 최적화5.8 철근 자르기5.9 0 -1 배낭5.10 최장 회문 부분 수열의 길이5.11 달걀 낙하 퍼즐[PART 4 부록은 덤이다]APPENDIX A 알고리즘의 효율성(시간과 공간 복잡도)A.1 알고리즘의 시간 복잡도A.2 시간 복잡도와 빅오 표기법A.3 공간 복잡도A.4 마치며APPENDIX B 코딜리티 활용하기B.1 코딜리티 소개 및 실습B.2 코딜리티 이용 팁
