자료검색

책소개

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

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

목차

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