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

알고리즘 공부의 걸림돌 극복하기 

다이내믹 프로그래밍을 이보다 더 자세히 설명한 책은 없다

재귀, 정렬, 검색까지 순조롭게 알고리즘을 공부하다 마주치는 첫 번째 장벽이 바로 다이내믹 프로그래밍(동적 계획법)이다. 재귀에서 다이내믹 프로그래밍으로 사고를 바로 전환하기가 어렵다 보니 많은 사람이 여기서 좌절하게 된다. 하지만 이 걸림돌을 제대로 마스터하기만 한다면 올림피아드 문제도 코딩 인터뷰도 누구보다 빠르게 남들과는 다르게 돌파할 수 있다. 

이 책은 알고리즘 공부의 걸림돌을 디딤돌로 만들기 위해, 코딩 면접 광탈에서 멘탈갑으로 거듭나기 위해 다이내믹 프로그래밍이라는 한 주제만을 처음부터 끝까지 철저히 파고든다. 재귀 호출, 메모 전략, 다이내믹 프로그래밍 세 가지 개념을 자세히 설명하고, 문제 풀이에 이들을 적용해 성능을 개선해나가는 전략을 익힐 수 있다. 

1장에서는 제곱, 하노이의 탑, 피보나치 수열, 최소 비용 등 고전적인 문제의 풀이법을 재귀적 사고로 구체화하는 방법을 배우고, 재귀와 메모리 구조의 관계를 이해함으로써 재귀의 한계를 깨닫게 한다. 2장은 ‘최적의 하위 구조’와 ‘하위 문제의 반복 계산’이라는 재귀의 두 가지 특성을 살펴보고, 캐시로 재귀를 개선하는 메모 전략을 배운다. 

3장은 부분 수열, 계승, 이진 트리 등의 예제로 하향식인 재귀와 메모 전략을 대체할 수 있는 상향식 다이내믹 프로그래밍을 배운다. 4장은 문제가 주어졌을 때 재귀와 메모 전략으로 시작해 다이내믹 프로그래밍으로 개선해나가는 문제 풀이 전략을 다룬다. 행렬 내 최소 이동 비용, 타일로 공터 채우기, 특정 점수에 도달하는 경우의 수, 최대 부분 배열 같은 문제를 풀며 전략을 확실히 손에 익힐 수 있다. 

5장은 최소 교정 비용, 직사각형 내 총 경로 수, 문자열 인터리빙, 부분집합의 합, 최장 공통 부분 수열, 거스름돈, 철근 자르기, 0-1 배낭, 달걀 낙하 퍼즐 등 인터뷰에 단골로 나오는 실전 문제를 풀어본다. 각 문제에 대해 재귀 및 메모 전략을 먼저 적용해보고, 이어서 다이내믹 프로그래밍을 개선하는 방식으로 문제 풀이의 감을 확실히 익힐 수 있다. 

원서는 두뇌 강국 인도에서 쓰여 인도 화폐나 지명이 사용되었지만 역자를 갈아 넣어 한국 실정에 맞게 초월번역했다. 많은 오류를 바로잡고 설명과 그림을 추가했으며, 원서 예제는 C 코드로 작성되었으나 역자가 밤을 새워 파이썬 버전 코드도 작성해 깃허브로 제공한다. 

책의 편집은 다이내믹 프로그래밍 때문에 컴공과에 못 가고 출판사에서 일하는 기획자가 혼신을 다해 맡았다. 동병상련의 마음으로 조금이라도 더 독자가 읽기 쉬운 책을 만들기 위해 열렬히 야근하며 편집했다. 그때 이 책만 있었어도 컴공과에 들어갔을 텐데…