다이내믹 프로그래밍 완전정복 (빠르고 우아한 상향식 문제 풀이법)

다이내믹 프로그래밍 완전정복 (빠르고 우아한 상향식 문제 풀이법)

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

미나크시

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

목차

[PART1재귀호출의모든것]

CHAPTER01재귀호출의이해
1.1재귀접근방법이란?
__예제:1에서n까지양의정수의합을계산하기
__예제:점화식으로제곱계산하기
__예제:하노이의탑
__선행재귀와후행재귀
__재귀를사용한문제해결
1.2재귀호출과메모리
__프로세스주소공간
__재귀호출을사용할때와사용하지않을때의메모리상태비교
__메모리배치를알면문제풀이에도움이됩니다
__마치며

CHAPTER02재귀호출의특징과메모전략
2.1최적의하위구조
__다이내믹프로그래밍에서최적의하위구조활용하기
2.2하위문제의반복계산
__예제:피보나치수열
__예제:역사이최소비용구하기
2.3메모전략


[PART2드디어다이내믹프로그래밍]

CHAPTER03다이내믹프로그래밍의이해
3.1다이내믹프로그래밍이란?
__예제:부분문자열다루기
3.2하향식접근방법과상향식접근방법
__예제:계승함수
__예제:이진트리
__상향식다이내믹프로그래밍이좋지않은경우

CHAPTER04다이내믹프로그래밍적용전략
4.1세방법을차례대로적용하며문제풀기
__예제:행렬에서최소이동비용구하기
4.2다이내믹프로그래밍을사용한문제해결
__다이내믹프로그래밍을적용할수있을까요?
__다이내믹프로그래밍으로문제풀기
__예제:타일로공터채우기
__예제:특정점수에도달하는경우의수구하기
__예제:연속된부분배열의최댓값구하기


[PART3지금부터게임을시작하지]

CHAPTER05실전문제
5.1최소교정비용문제
5.2직사각형에서총경로수구하기
5.3문자열인터리빙확인문제
5.4부분집합의합구하기
5.5최장공통부분수열길이구하기
5.6최장공통부분수열출력하기
5.7거스름돈최적화
5.8철근자르기
5.90-1배낭
5.10최장회문부분수열의길이
5.11달걀낙하퍼즐


[PART4부록은덤이다]

APPENDIXA알고리즘의효율성(시간과공간복잡도)
A.1알고리즘의시간복잡도
A.2시간복잡도와빅오표기법
A.3공간복잡도
A.4마치며

APPENDIXB코딜리티활용하기
B.1코딜리티소개및실습
B.2코딜리티이용팁

출판사 서평

알고리즘공부의걸림돌극복하기
다이내믹프로그래밍을이보다더자세히설명한책은없다
재귀,정렬,검색까지순조롭게알고리즘을공부하다마주치는첫번째장벽이바로다이내믹프로그래밍(동적계획법)이다.재귀에서다이내믹프로그래밍으로사고를바로전환하기가어렵다보니많은사람이여기서좌절하게된다.하지만이걸림돌을제대로마스터하기만한다면올림피아드문제도코딩인터뷰도누구보다빠르게남들과는다르게돌파할수있다.
이책은알고리즘공부의걸림돌을디딤돌로만들기위해,코딩면접광탈에서멘탈갑으로거듭나기위해다이내믹프로그래밍이라는한주제만을처음부터끝까지철저히파고든다.재귀호출,메모전략,다이내믹프로그래밍세가지개념을자세히설명하고,문제풀이에이들을적용해성능을개선해나가는전략을익힐수있다.

1장에서는제곱,하노이의탑,피보나치수열,최소비용등고전적인문제의풀이법을재귀적사고로구체화하는방법을배우고,재귀와메모리구조의관계를이해함으로써재귀의한계를깨닫게한다.2장은‘최적의하위구조’와‘하위문제의반복계산’이라는재귀의두가지특성을살펴보고,캐시로재귀를개선하는메모전략을배운다.
3장은부분수열,계승,이진트리등의예제로하향식인재귀와메모전략을대체할수있는상향식다이내믹프로그래밍을배운다.4장은문제가주어졌을때재귀와메모전략으로시작해다이내믹프로그래밍으로개선해나가는문제풀이전략을다룬다.행렬내최소이동비용,타일로공터채우기,특정점수에도달하는경우의수,최대부분배열같은문제를풀며전략을확실히손에익힐수있다.
5장은최소교정비용,직사각형내총경로수,문자열인터리빙,부분집합의합,최장공통부분수열,거스름돈,철근자르기,0-1배낭,달걀낙하퍼즐등인터뷰에단골로나오는실전문제를풀어본다.각문제에대해재귀및메모전략을먼저적용해보고,이어서다이내믹프로그래밍을개선하는방식으로문제풀이의감을확실히익힐수있다.

원서는두뇌강국인도에서쓰여인도화폐나지명이사용되었지만역자를갈아넣어한국실정에맞게초월번역했다.많은오류를바로잡고설명과그림을추가했으며,원서예제는C코드로작성되었으나역자가밤을새워파이썬버전코드도작성해깃허브로제공한다.
책의편집은다이내믹프로그래밍때문에컴공과에못가고출판사에서일하는기획자가혼신을다해맡았다.동병상련의마음으로조금이라도더독자가읽기쉬운책을만들기위해열렬히야근하며편집했다.그때이책만있었어도컴공과에들어갔을텐데…

[주요내용]
● 재귀호출의AtoZ
● 재귀호출과메모리구조의관계
● 최적의하위구조+하위문제의반복계산
● 메모전략을활용한재귀호출성능개선
● 하향식접근vs상향식접근
● 다이내믹프로그래밍기초부터문제풀이전략까지
● 부분집합의합,최장공통부분수열,0-1배낭,회문등실전문제풀이