다이내믹 프로그래밍 완전정복

빠르고 우아한 상향식 문제 풀이법

미나크시 , 카말 라와트 지음 | 박상은 옮김

한빛미디어 2019년 10월 29일 출간 종이책 : 2019년 10월 04일 출간

작품소개

책소개

빠르고 우아한 상향식 문제 풀이법으로
코딩 면접 광탈에서 멘탈갑으로 거듭나기

다이내믹 프로그래밍(동적 계획법)은 알고리즘을 공부하다 마주치는 첫 번째 큰 장벽이다. 이 책은 알고리즘 공부의 걸림돌을 디딤돌로 만들기 위해 다이내믹 프로그래밍이라는 한 가지 주제만을 철저히 파고든다. 재귀 호출, 메모 전략, 상향식 다이내믹 프로그래밍의 개념을 자세히 설명하고, 고전 알고리즘 문제부터 단골 인터뷰 문제까지 다양한 예제에 세 가지 방법을 적용해본다. 늘 헷갈리던 개념을 확실히 이해하고, 문제 풀이에 적용할 수 있게 될 것이다.

목차

[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 코딜리티 이용 팁

작가정보

저자(글) 미나크시

저자 : 미나크시
코딩 인터뷰 전문 스타트업 리탐바라 테크놀로지(www.ritambhara.in)의 공동설립자. 컴퓨터사이언스 석사 학위가 있으며 기술 스타트업 창업가, 공인 요가 트레이너, 두 아이의 엄마 등 역할이 많지만 워라밸을 잘 유지하고 있다. 말하자면 삶 속에서 문제 풀이와 최적화를 실천하고 있다.

저자 : 카말 라와트
소프트웨어 개발자이자 교육자, 저술가, 사업가. 다양한 분야와 플랫폼에 걸쳐 대규모 데스크톱, 클라우드, 모바일 애플리케이션의 전체 수명주기를 구현한 경력이 있다. MS 원노트, 어도비 포토샵, 삼성 갤럭시 커넥트 등 난도가 높은 프로젝트의 기술 아키텍트를 역임했다. MS, 어도비 및 많은 스타트업에서 핵심 인터뷰어를 맡기도 했다. MS에서 시니어 SDE로 근무하다 2006년부터 학생들에게 프로그래밍 인터뷰 돌파법을 코칭하고 있다.

역자 : 박상은
컴퓨터에 붙은 그림을 보고 애플이라는 단어의 뜻을 알게 된 이 땅의 흔한 개발자다. 포항공과대학교에서 전산학을, 한국과학기술원에서 인공지능을 공부한 덕분에 알파고와 스카이넷을 구분할 줄 아는 지혜를 갖추게 되었다. 메일, 브라우저, CMS, 도서 관리 시스템 등 일관성 없이 다양한 프로젝트에 참여했다. 이렇게 하여 물에 물 탄 듯한 경력이 완성되는 듯했으나, 최근 몇 년은 빅데이터 처리 관련 연구 개발에 집중했다. 현재 인공지능연구원의 Field AI팀 팀장으로 딥러닝을 활용해서 개인과 기업에 도움이 되는 서비스를 개발하고 있다. 특히 자연어 데이터와 금융 데이터를 딥러닝과 빅데이터 기술을 활용하여 분석하는 문제를 고민 중이다.

저자(글) 카말 라와트

번역 박상은