도서소개
알고리즘 공부의 걸림돌 극복하기
다이내믹 프로그래밍을 이보다 더 자세히 설명한 책은 없다
재귀, 정렬, 검색까지 순조롭게 알고리즘을 공부하다 마주치는 첫 번째 장벽이 바로 다이내믹 프로그래밍(동적 계획법)이다. 재귀에서 다이내믹 프로그래밍으로 사고를 바로 전환하기가 어렵다 보니 많은 사람이 여기서 좌절하게 된다. 하지만 이 걸림돌을 제대로 마스터하기만 한다면 올림피아드 문제도 코딩 인터뷰도 누구보다 빠르게 남들과는 다르게 돌파할 수 있다.
이 책은 알고리즘 공부의 걸림돌을 디딤돌로 만들기 위해, 코딩 면접 광탈에서 멘탈갑으로 거듭나기 위해 다이내믹 프로그래밍이라는 한 주제만을 처음부터 끝까지 철저히 파고든다. 재귀 호출, 메모 전략, 다이내믹 프로그래밍 세 가지 개념을 자세히 설명하고, 문제 풀이에 이들을 적용해 성능을 개선해나가는 전략을 익힐 수 있다.
1장에서는 제곱, 하노이의 탑, 피보나치 수열, 최소 비용 등 고전적인 문제의 풀이법을 재귀적 사고로 구체화하는 방법을 배우고, 재귀와 메모리 구조의 관계를 이해함으로써 재귀의 한계를 깨닫게 한다. 2장은 '최적의 하위 구조'와 '하위 문제의 반복 계산'이라는 재귀의 두 가지 특성을 살펴보고, 캐시로 재귀를 개선하는 메모 전략을 배운다.
3장은 부분 수열, 계승, 이진 트리 등의 예제로 하향식인 재귀와 메모 전략을 대체할 수 있는 상향식 다이내믹 프로그래밍을 배운다. 4장은 문제가 주어졌을 때 재귀와 메모 전략으로 시작해 다이내믹 프로그래밍으로 개선해나가는 문제 풀이 전략을 다룬다. 행렬 내 최소 이동 비용, 타일로 공터 채우기, 특정 점수에 도달하는 경우의 수, 최대 부분 배열 같은 문제를 풀며 전략을 확실히 손에 익힐 수 있다.
5장은 최소 교정 비용, 직사각형 내 총 경로 수, 문자열 인터리빙, 부분집합의 합, 최장 공통 부분 수열, 거스름돈, 철근 자르기, 0-1 배낭, 달걀 낙하 퍼즐 등 인터뷰에 단골로 나오는 실전 문제를 풀어본다. 각 문제에 대해 재귀 및 메모 전략을 먼저 적용해보고, 이어서 다이내믹 프로그래밍을 개선하는 방식으로 문제 풀이의 감을 확실히 익힐 수 있다.
원서는 두뇌 강국 인도에서 쓰여 인도 화폐나 지명이 사용되었지만 역자를 갈아 넣어 한국 실정에 맞게 초월번역했다. 많은 오류를 바로잡고 설명과 그림을 추가했으며, 원서 예제는 C 코드로 작성되었으나 역자가 밤을 새워 파이썬 버전 코드도 작성해 깃허브로 제공한다.
책의 편집은 다이내믹 프로그래밍 때문에 컴공과에 못 가고 출판사에서 일하는 기획자가 혼신을 다해 맡았다. 동병상련의 마음으로 조금이라도 더 독자가 읽기 쉬운 책을 만들기 위해 열렬히 야근하며 편집했다. 그때 이 책만 있었어도 컴공과에 들어갔을 텐데…
주요 내용
● 재귀 호출의 A to Z
● 재귀 호출과 메모리 구조의 관계
● 최적의 하위 구조 + 하위 문제의 반복 계산
● 메모 전략을 활용한 재귀 호출 성능 개선
● 하향식 접근 vs 상향식 접근
● 다이내믹 프로그래밍 기초부터 문제 풀이 전략까지
● 부분집합의 합, 최장 공통 부분 수열, 0-1 배낭, 회문 등 실전 문제 풀이
도서목차
[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 코딜리티 이용 팁
해시태그
#분철무료 #다이내믹 #프로그래밍 #완전 #정복
로그인
즐겨찾기
