[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
알고리즘 공부의 걸림돌 극복하기
다이내믹 프로그래밍을 이보다 더 자세히 설명한 책은 없다
재귀, 정렬, 검색까지 순조롭게 알고리즘을 공부하다 마주치는 첫 번째 장벽이 바로 다이내믹 프로그래밍(동적 계획법이다. 재귀에서 다이내믹 프로그래밍으로 사고를 바로 전환하기가 어렵다 보니 많은 사람이 여기서 좌절하게 된다. 하지만 이 걸림돌을 제대로 마스터하기만 한다면 올림피아드 문제도 코딩 인터뷰도 누구보다 빠르게 남들과는 다르게 돌파할 수 있다.
이 책은 알고리즘 공부의 걸림돌을 디딤돌로 만들기 위해, 코딩 면접 광탈에서 멘탈갑으로 거듭나기 위해 다이내믹 프로그래밍이라는 한 주제만을 처음부터 끝까지 철저히 파고든다. 재귀 호출, 메모 전략, 다이내믹 프로그래밍 세 가지 개념을 자세히 설명하고, 문제 풀이에 이들을 적용해 성능을 개선해나가는 전략을 익힐 수 있다.
1장에서는 제곱, 하노이의 탑, 피보나치 수열, 최소 비용 등 고전적인 문제의 풀이법을 재귀적 사고로 구체화하는 방법을 배우고, 재귀와 메모리 구조의 관계를 이해함으로써 재귀의 한계를 깨닫게 한다. 2장은 ‘최적의 하위 구조’와 ‘하위 문제의 반복 계산’이라는 재귀의 두 가지 특성을 살펴보고, 캐시로 재귀를 개선하는 메모 전략을 배운다.
3장은 부분 수열, 계승, 이진 트리 등의 예제로 하향식인 재귀와 메모 전략을 대체할 수 있는 상향식 다이내믹 프로그래밍을 배운다. 4장은 문제가 주어졌을 때 재귀와 메모 전략으로 시작해 다이내믹 프로그래밍으로 개선해나가는 문제 풀이 전략을 다룬다. 행렬 내 최소 이동 비용, 타일로 공터 채우기, 특정 점수에 도달하는 경우의 수, 최대 부분 배열 같은 문제를 풀며 전략을 확실히 손에 익힐 수 있다.
5장은 최소 교정 비용, 직사각형 내 총 경로 수, 문자열 인터리빙, 부분집합의 합, 최장 공통 부분 수열, 거스름돈, 철근 자르기, 0-1 배낭, 달걀 낙하 퍼즐 등 인터뷰에 단골로 나오는 실전 문제를 풀어본다. 각 문제에 대해 재귀 및 메모 전략을 먼저 적용해보고,
