다이내믹 프로그래밍(동적 계획법)은 알고리즘을 공부하다 마주치는 첫 번째 큰 장벽이다. 이 책은 알고리즘 공부의 걸림돌을 디딤돌로 만들기 위해 다이내믹 프로그래밍이라는 한 가지 주제만을 철저히 파고든다. 재귀 호출, 메모 전략, 상향식 다이내믹 프로그래밍의 개념을 자세히 설명하고, 고전 알고리즘 문제부터 단골 인터뷰 문제까지 다양한 예제에 세 가지 방법을 적용해본다. 늘 헷갈리던 개념을 확실히 이해하고, 문제 풀이에 적용할 수 있게 될 것이다.
주요 내용
재귀 호출의 A to Z
재귀 호출과 메모리 구조의 관계
최적의 하위 구조 + 하위 문제의 반복 계산
메모 전략을 활용한 재귀 호출 성능 개선
하향식 접근 vs 상향식 접근
다이내믹 프로그래밍 기초부터 문제 풀이 전략까지
부분집합의 합, 최장 공통 부분 수열, 0-1 배낭, 회문 등 실전 문제 풀이
저자소개
저자
미나크시
코딩 인터뷰 전문 스타트업 리탐바라 테크놀로지(www.ritambhara.in)의 공동설립자. 컴퓨터사이언스 석사 학위가 있으며 기술 스타트업 창업가, 공인 요가 트레이너, 두 아이의 엄마 등 역할이 많지만 워라밸을 잘 유지하고 있다. 말하자면 삶 속에서 문제 풀이와 최적화를 실천하고 있다.
저자
카말 라와트
소프트웨어 개발자이자 교육자, 저술가, 사업가. 다양한 분야와 플랫폼에 걸쳐 대규모 데스크톱, 클라우드, 모바일 애플리케이션의 전체 수명주기를 구현한 경력이 있다. MS 원노트, 어도비 포토샵, 삼성 갤럭시 커넥트 등 난도가 높은 프로젝트의 기술 아키텍트를 역임했다. MS, 어도비 및 많은 스타트업에서 핵심 인터뷰어를 맡기도 했다. MS에서 시니어 SDE로 근무하다 2006년부터 학생들에게 프로그래밍 인터뷰 돌파법을 코칭하고 있다.
역자
박상은
컴퓨터에 붙은 그림을 보고 애플이라는 단어의 뜻을 알게 된 이 땅의 흔한 개발자다. 포항공과대학교에서 전산학을, 한국과학기술원에서 인공지능을 공부한 덕분에 알파고와 스카이넷을 구분할 줄 아는 지혜를 갖추게 되었다. 메일, 브라우저, CMS, 도서 관리 시스템 등 일관성 없이 다양한 프로젝트에 참여했다. 이렇게 하여 물에 물 탄 듯한 경력이 완성되는 듯했으나, 최근 몇 년은 빅데이터 처리 관련 연구 개발에 집중했다. 현재 인공지능연구원의 Field AI팀 팀장으로 딥러닝을 활용해서 개인과 기업에 도움이 되는 서비스를 개발하고 있다. 특히 자연어 데이터와 금융 데이터를 딥러닝과 빅데이터 기술을 활용하여 분석하는 문제를 고민 중이다.
재귀, 정렬, 검색까지 순조롭게 알고리즘을 공부하다 마주치는 첫 번째 장벽이 바로 다이내믹 프로그래밍(동적 계획법)이다. 재귀에서 다이내믹 프로그래밍으로 사고를 바로 전환하기가 어렵다 보니 많은 사람이 여기서 좌절하게 된다. 하지만 이 걸림돌을 제대로 마스터하기만 한다면 올림피아드 문제도 코딩 인터뷰도 누구보다 빠르게 남들과는 다르게 돌파할 수 있다.
이 책은 알고리즘 공부의 걸림돌을 디딤돌로 만들기 위해, 코딩 면접 광탈에서 멘탈갑으로 거듭나기 위해 다이내믹 프로그래밍이라는 한 주제만을 처음부터 끝까지 철저히 파고든다. 재귀 호출, 메모 전략, 다이내믹 프로그래밍 세 가지 개념을 자세히 설명하고, 문제 풀이에 이들을 적용해 성능을 개선해나가는 전략을 익힐 수 있다.
1장에서는 제곱, 하노이의 탑, 피보나치 수열, 최소 비용 등 고전적인 문제의 풀이법을 재귀적 사고로 구체화하는 방법을 배우고, 재귀와 메모리 구조의 관계를 이해함으로써 재귀의 한계를 깨닫게 한다. 2장은 ‘최적의 하위 구조’와 ‘하위 문제의 반복 계산’이라는 재귀의 두 가지 특성을 살펴보고, 캐시로 재귀를 개선하는 메모 전략을 배운다.
3장은 부분 수열, 계승, 이진 트리 등의 예제로 하향식인 재귀와 메모 전략을 대체할 수 있는 상향식 다이내믹 프로그래밍을 배운다. 4장은 문제가 주어졌을 때 재귀와 메모 전략으로 시작해 다이내믹 프로그래밍으로 개선해나가는 문제 풀이 전략을 다룬다. 행렬 내 최소 이동 비용, 타일로 공터 채우기, 특정 점수에 도달하는 경우의 수, 최대 부분 배열 같은 문제를 풀며 전략을 확실히 손에 익힐 수 있다.
5장은 최소 교정 비용, 직사각형 내 총 경로 수, 문자열 인터리빙, 부분집합의 합, 최장 공통 부분 수열, 거스름돈, 철근 자르기, 0-1 배낭, 달걀 낙하 퍼즐 등 인터뷰에 단골로 나오는 실전 문제를 풀어본다. 각 문제에 대해 재귀 및 메모 전략을 먼저 적용해보고, 이어서 다이내믹 프로그래밍을 개선하는 방식으로 문제 풀이의 감을 확실히 익힐 수 있다.
원서는 두뇌 강국 인도에서 쓰여 인도 화폐나 지명이 사용되었지만 역자를 갈아 넣어 한국 실정에 맞게 초월번역했다. 많은 오류를 바로잡고 설명과 그림을 추가했으며, 원서 예제는 C 코드로 작성되었으나 역자가 밤을 새워 파이썬 버전 코드도 작성해 깃허브로 제공한다.
책의 편집은 다이내믹 프로그래밍 때문에 컴공과에 못 가고 출판사에서 일하는 기획자가 혼신을 다해 맡았다. 동병상련의 마음으로 조금이라도 더 독자가 읽기 쉬운 책을 만들기 위해 열렬히 야근하며 편집했다. 그때 이 책만 있었어도 컴공과에 들어갔을 텐데…
옆구리 혹은 가방안의 알고리즘 문제 풀이 책에서 절대 빠지지 않는 부분이 다이나믹 프로그래밍 부분인데 알고리즘 문제 풀이에서 절대 빠질수 없는 부분이니 만큼 설명도 방대하고 예제들 또한 이해하기도 어렵다.
이 책은 다이나믹 프로그래밍 부분을 아예 따로 뽑아내 설명을 하고 있다. 여러 유형의 문제에 대해 다양한 방법을 설명하는 다른 책들과는 달리 다이나믹 프로그래밍에 한가지 방법에 대해 쉽고 명확한 설명을 목표로 한다. 책도 생각보다 얇으며 책의 문체가 편해 책을 읽기에도 부담이 적다.
많은 회사들이 S/W 개발자를 필요로 하면서 그에 함께 정확한 역량 측정을 위한 지표로써 알고리즘 문제 풀이를 활용한다. 알고리즘 문제 풀이와 개발 역량과의 직접적인 관계가 있는지는 잘모르겠으나 구직을 준비하는 사람들에 입장에서는 무시할 수 없는 것이 사실이다.
프로그래밍의 많은 세부 분야 중 알고리즘 보다 다른 영역에서 더 흥미를 느끼고 역량이 드러날수 있음에도 불구하고 역량 평가의 지표로써 활용되기에 어떤 식으로든 어느정도의 지식을 습득하고 시험에 대비해야 하는 것이 현실이다.
때론 의사와는 무관하게 하고 싶은 것을 하는 것이 아니라 해야 해서 하는 상황이 들이 닥치기도 하지만 때론 의사와는 무관하게 우연히 새로운 지식을 접하고 새로운 즐거움을 알게 되는 계기가 되기도 한다.
나는 다이내믹 프로그래밍이 정확히 무엇을 의미하는지 전혀 알지 못하는 상태였기 때문에 약간의 부담감을 안고 책을 읽기 시작했는데, 그런 나에게 이 책은 다이내믹 프로그래밍이 무엇인지에 대해서 맛볼 수 있는 중요한 기회를 선사해주었다.
일단 책의 처음은 재귀에 대한 내용으로 시작한다. 재귀의 경우 꽤나 자주 접했기에 비교적 쉽게 이해할 수 있었다. 책의 내용 중에서 재귀를 사용할 때 주의해야할 것에 대해서 아래와 같이 나와있었다.
재귀에는 항상 종료 조건이 있어야 한다. 종료 조건이 없으면 재귀 호출이 무한히 반복된다.
재귀 함수는 전체 작업의 일부만 수행하고 나머지는 재귀 호출에 위임한다.
어찌보면 너무나 당연한 이야기였지만, 너무나 당연하기 때문에 간과할 수 있는 부분에 대해서 명확하게 짚어주고 있었다.
또한 재귀에 대해 설명하면서 아래와 같은 말도 덧붙이고 있었다.
쉬운 코드와 복잡한 코드 중에 선택해야 한다면, 성능이나 메모리의 이점이 있지 않은 한 쉬운 코드가 좋습니다.
같은 문제를 비슷한 노력으로 해결할 수 있다면 재귀 호출을 사용하지 않는 쪽으로 구현하는 것이 바람직합니다. 만들어진 프로그램을 실행하보면 재귀 호출을 사용하지 않는 경우가 실행도 빠르고 필요한 메모리의 양도 작습니다.
깊이 공감한다. 정말 명확한 이유가 있지 않은 한 재귀 호출을 남발하는 것은 좋지 않다고 생각한다. 물론 재귀 호출로 문제를 푸는 것이 우아하고 세련된 방법처럼 보일 수 있지만, 재귀 호출은 이를 사용하지 않는 경우에 비해 일반적으로 더 많은 비용이 들기 때문이다.
이어서 선행 재귀와 후행 재귀에 대해서도 설명해주고 있는데, 연결 리스트의 탐색 예제를 통해 설명해주는 부분이 나름 직관적으로 와닿았다.
그리고 재귀 호출과 메모리에 대한 내용이 있었는데, 특히 프로세스 주소 공간에 대한 설명은 꽤나 유용했다. 코드 영역, 데이터 영역, 스택 영역, 힙 영역 각각에 대해 간략하지만 핵심적인 설명이 있었으며 특히나 프로그램의 로딩부터 함수의 호출로 인한 메모리의 변화가 어떻게 일어나는지에 대해 설명하는 부분이 유용하다고 느껴졌다.
재귀를 사용할 때와 사용하지 않을 때 메모리의 상태 비교를 통해 책에서는 아래와 같이 이야기한다.
재귀 호출을 사용하면 메모리와 실행 시간 양 측면에서 비용이 증가합니다.
이에 이어 다음으로는 재귀 접근 방식이 가지는 두 가지 특징에 대해서 언급하는데 그 첫번째는 최적의 하위 구조로, 아래와 같이 설명하고 있다.
어떤 문제의 풀이법을 같은 문제의 더 작은 문제로 정의하는 게 최적의 풀이법이라면 이 문제는 최적의 하위 구조를 가졌다고 합니다. 최적의 하위 구조를 가진 문제는 다이내믹 프로그래밍 방법을 적용하기 좋은 문제입니다.
그리고 두번째 특징으로는 하위 문제의 반복 계산에 대해서 언급하는데, 책의 본문에서는 피보나치 수열 계산 문제에서의 하위 문제의 반복 계산을 예로 들고 있다. 그리고 이어서 하위 문제의 반복 계산이 발생하여 수행 시간이 증가하는 문제를 해결하기 위한 방법으로 메모 전략(메모이제이션)을 소개하는데, 이를 쉽게 말하면 어떤 하위 문제를 계산했을 때 그 결과를 일종의 캐시에 저장하여 같은 하위 문제를 다시 풀 때 이미 저장된 결과를 사용하는 방식을 의미한다. 또한 메모 전략에 대해서 아래와 같이 언급하고 있다.
메모 전략도 재귀 접근 방법에 속합니다.
메모 전략 = 재귀 호출 + 캐시 - 하위 문제의 반복 계산.
이어서 드디어 주인공인 다이내믹 프로그래밍에 대한 내용이 본격적으로 등장하는데, 가장 처음 알게된 것은 문제 해결의 방향이 재귀 호출, 또는 메모 전략은 하향식인 반면 다이내믹 프로그래밍은 상향식이라는 사실이었다.
앞에서 재귀 호출 또는 메모 전략을 통해 풀었던 예제들을 보여주면서 이를 다이내믹 프로그래밍으로 해결할 수 있음을 보여주는데, 이와 함께 직접 깃헙에 재귀 호출, 메모 전략, 다이내믹 프로그래밍의 실행 시간을 비교해볼 수 있는 예제 코드를 올려놨다는 점이 좋았다.
동일한 문제를 각각 하향식 접근 방법과 상향식 접근 방법로 풀어내는 예제 코드들로 하여금 그 둘이 어떤 차이점을 가지는지를 비교해볼 수 있었다.
그리고 결론적으로 다이내믹 프로그래밍은 재귀 호출 자체로부터 발생하는 부하를 피하기 위해 상향식으로 문제를 해결할 수 있다, 라는 내용을 전달하고 있었다.
더 나아가 그렇다고 다이내믹 프로그래밍이 은탄환은 아니라는 것에 대해서 설명해주는데, 하향식 접근 방법에서는 모든 하위 문제를 풀지 않고 전체 문제의 해답을 얻을 때 필요한 하위 문제만 풀었으나 상향식인 다이내믹 프로그래밍에서는 모든 하위 문제에 대해 계산을 수행하여 드물게 실제 필요한 것보다 훨씬 더 많은 하위 문제를 풀어야 하는 부작용이 발생하기도 한다는 점에 대해서 설명해주고 있다.
이에 이어 다이내믹 프로그래밍이 어떤 것이다, 라는 설명에서 그치지 않고 실제로 어떻게 적용할 수 있는지를 알려주는데, 다이내믹 프로그래밍을 사용해서 문제를 푸는 기본적인 순서는 아래와 같이 알려주고 있다.
재귀 호출을 사용한 풀이법 작성.
다이내믹 프로그래밍이나 메모 전략을 사용해 풀이법 개선.
그리고 어떤 문제가 다이내믹 프로그래밍 적용 가능 여부를 확인할 수 있는 체크리스트도 아래와 같이 알려주고 있다.
문제가 최적의 하위 구조를 가지고 있는지.
하위 문제를 반복 계산하는지.
최적화, 최대화 또는 최소화나 어떤 작업의 경우의 수를 구하는 유형의 문제인지.
더불어 다이내믹 프로그래밍을 적용하기 위한 단계식 접근법도 친절하게 알려주고 있다.
다이내믹 프로그래밍 적용 가능한 경우인지 확인.
점화식 또는 재귀 과정 정의.
문제를 하위 문제를 사용해 하향식으로 정의.
맨 아래에 해당하는 기본 경우에 대한 답을 정의.
종료 조건 추가.
(선택적) 메모 전략 시도.
상향식으로 문제 풀이 도전.
위와 같이 실제로 적용할 수 있는 방법에 대해서도 설명해주고 있는 점이 상당히 유용하다고 느껴졌는데, 다이내믹 프로그래밍이 무엇인지 알았다고 해서 어디에 어떻게 사용해야 하는지 단번에 알 수 있는 건 아니라고 느꼈기 때문이다. 그리고 이러한 단계식 접근법을 여러 예제 문제들에 적용하는 과정을 보여주고 있다는 점에서 상당히 마음에 들었다.
이 책의 전체적인 소감은 이론적인 부분의 설명은 적당하게, 최대한 부담되지 않는 선에서 하면서 실제로 적용해볼 수 있는 여러 문제를 소개해주고 풀어내는 과정을 통해 재귀 호출과 메모 전략, 다이내믹 프로그래밍에 대해서 알려주는 실용적인 책, 이라는 것이었다. 본문 자체에도 꽤나 많은 예제들이 수록되어 있으며, 마지막 장인 5장은 아예 통째로 다양한 실전 문제들을 수록하여 위에서 안내해주는 단계식 접근법을 통해 풀어내는 과정을 보여주면서 연습문제를 통해 독자들 스스로도 한껏 두뇌를 사용할 수 있는 기회를 제공해주고 있다.
재귀 호출과 메모 전략, 다이내믹 프로그래밍에 대해서 관심이 있으나 아직 입문하지 못한 분들에게 추천하기 좋은 책이라는 생각이 든다.
" " 수학과 컴퓨터 공학, 그리고 경제학에서 동적 계획법(動的計劃法, dynamic programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다.
(위키백과)
이게뭐지.... 싶었습니다.
그리고,
근래 우연한 기회에 이 책을 입수하게 되었습니다. 책을 읽어보니 프로그래머 입장에서 "동적 계획법"을 어떻게 접근해야 하는 지 이해할 수 있었습니다.
일반적으로는 재귀함수를 사용해서 푸는 문제들이 다이내믹 프로그래밍의 대상이 되고요.
재귀함수는 사실 꼬리재귀에 대해 콜스텍을 소모하지 않게 언어에서 지원해주지 않으면, 쓰기 힘든 부분이 있는데요. 다이내믹 프로그래밍은 이를 다시 상향식으로 풀어서 더 빠르게 수행할 수 있는 방법을 제공해주는 이점이 있겠더군요.
저자는 단순히 다이내믹 프로그래밍을 설명하는데서 끝나지 않고,
알고리즘 예제를 몇 개 들면서, 독자가 충분히 그 과정을 이해할 수 있도록 배려하고 있습니다.
만약 알고리즘에 관심이 있는 독자라면 이 책을 천천히 읽으면서 도움을 받을 수 있을 것 같습니다.
학부 프로그래밍 수업 시간 초반에 나오는 것이 재귀함수이다. 보통은 팩토리얼을 구하는 방식으로 소개된다. 하지만, 나중에 프로그래밍을 깊게 배우게 되면, 재귀함수를 얼마나 조심히 써야 하는지를 배우게 된다.
하지만 개발자 생활을 15년 정도 해왔는데, 현업에서 재귀함수를 사용하는 경우는 많지는 않았다. 웹개발이 위주였는데백엔드 쪽에서 아주 가끔 쓰곤 했다. 하지만 실제로 팀원이 개발한 것을 보니, 이론을 제대로 공부 안했을 때 프로그램의성능이 얼마나 나빠질 수 있는지를 뼈져리게 느끼게 되었다. 그 뒤로 이러한 책을 종종 읽곤 한다.
<추천 대상>
A. 취업이나 이직을 준비하며 코딩 면접을 준비하는 사람
B. 서버 개발이나 백엔드 개발을 많이하며, 프로그래밍 시 성능이나 메모리 사용을 많이 고려해서 개발해야 하는 사람
<요약>
Part 1. 재귀호출
재귀호출에 대해서 설명을 한다. 점화식, 팩토리얼, 하노이탑, 피보나치수열 등의 많이 쓰이는 예제로 설명을 한다. 추가로 재귀호출을 할 때 메모리가 어떻게 쓰이는 지에 대해서도 설명을 한다. 실제 현업에서 개발을 하게 되면 성능만 생각할게 아니라 메모리 사용량에 대해서도 크게 생각해야 한다.
Part 2. 다이내믹 프로그래밍
다이내믹 프로그래밍의 개념에 대해서 설명한다. 피보나치 수열을 예로 들어 재귀, 다이내믹 프로그래밍, 메모 전략을 설명한다.
Part 3. 실전
Part 1, 2에서 배운 개념을 바탕으로 실전 예제를 위주로 설명을 한다. 여러 가지 예제를 들어가며 쉽게 설명한다. 앞의 1, 2파트에서 이론적으로 이해가 덜 갔던 부분들도 실제 예제를 보면서 이해될 수 있다.
<마치며>
항상 그러하지만 학부 때 이론적으로 배운 것이 현업에서 얼마나 도움이 될까 고민하곤 한다. 하지만 실제 고성능을 요구하는 프로그래밍을 해야 하는 경우에는 이론적으로 공부했던 내용이 크게 도움이 되곤 한다. 이러한 면에서 성능을 고민해야 하는 사람들에게는 큰 도움이 될 것이라 생각한다.
‘다이내믹 프로그래밍’이라고 하면 프로그래밍하는 방법이나 이와 관련된어떤 것을 떠올리기 쉽다. 또는 ‘다이내믹’이라고 하는 언어가 있나? 하는 생각을 할 수 도 있다. 하지만 다이내믹 프로그래밍은 ‘동적 계획법’으로 알려진 문제 풀이 방식을 뜻한다. C, Java 와 같은 프로그래밍언어를 이용해서 코드를 작성하는 것은 주어진 문제를 푸는 과정에서 풀이 방법을 컴퓨터가 알아 들을 수 있도록 형식화하는 일이다. 이 책이 인도 사람(?)인 미나크시와 카말 라와트에 의해 영어로작성되었고, 그 책을 박상은 님이 우리말로 옮겼다. 다이내믹프로그래밍에 대한 내용을 전하고자 하는 같은 목적을 영어와 우리말이라는 서로 다른 형태로 나타낸 것과 같다. 책이어떤 언어로 쓰였느냐 보다 어떤 내용의 책이냐가 더 중요한 것처럼, 어떤 언어를 사용했느냐 보다 어떤방식으로 문제를 푸느냐에 집중할 필요가 있다.
이책은 문제를 푸는 방법에 대한 이야기를 다루고 있다. 특히 보다 효율적으로 문제를 푸는 방법에 대한것이다. 단순히 정답을 얻는 것에 그치지 않고, 어떻게 하면더 빠르게, 더 적은 메모리로 문제를 풀 수 있을 지 고민하고 있다.예를 들어 역 사이 최소 요금 문제의 경우, 15개의 역에 대해 일반적인 재귀 방식으로문제를 풀면 535 msec이 걸리는 반면, 메모 전략을이용하면 1 msec 이 채 걸리지 않는다. 또한 250개의 역에 대해 메모 전략이 1492 msec 이 걸리지만, 다이내믹 프로그래밍을 적용하면 4 msec 만 소요됨을 나타내고있다. 그렇다고 언제나 다이내믹 프로그래밍이 최선의 결과를 가져오는 것은 아님을 이 책은 분명히 하고있다. 250개 중에서 10개를 추출하는 방법의 수를 나타내는조합(Combination)의 경우, 메모 전략의 경우 2msec이 걸린 반면, 다이내믹 프로그래밍은 9msec의 시간이 필요했다. 상향식 다이내믹 프로그래밍에서는 전체문제의 풀이에 도달하기 전 모든 하위 문제에 대해서 계산을 수행하게 되고, 따라서 드물게는 실제 필요한것보다 훨씬 더 많은 하위 문제를 풀어야 하는 경우가 생길 수 있는 것이다.
이책은 크게 4개의 파트로 구성되어 있다. 첫번째 파트에서는재귀 호출에 대한 전반적인 이해를 돕고, 두번째 파트에서 다이내믹 프로그래밍에 대해 소개하며 적용 전략을다룬다. 세번째 파트는 실전 문제를 기반으로 재귀 호출로 푸는 방법과 다이내믹 프로그래밍을 이용한 방법에대해 이야기한다. 끝으로 네번째 파트는 원서에는 없지만 책의 내용을 보다 쉽게 이해할 수 있도록 하는시간, 공간 복잡도에 대한 기본 내용과 더불어 온라인 코딩 테스트 환경을 체험해 볼 수 있는 코딜리티사이트에 대한 간략한 소개로 마무리하고 있다.
‘좋은개발자가 되려면 프로그래밍 언어를 배우는 것보다 문제 해결의 기술을 습득하는 것이 중요합니다.’ 책의서문에 있는 말이다. 좋은 개발자를 꿈꾼다면 곁에 두고 자주 꺼내어 보길 추천한다.
<다이내믹 프로그래밍 완전 정복>의 처음 세 장은 재귀부터 시작하여 간단한 문제만을 다루고 있습니다. 기본 개념을 설명하고 독자가 쉽게 이해할 수 있도록 복잡한 부분을 과감히 배제하고 있습니다. 이후에는 조금씩 복잡한 문제를 다루고 마지막에는 실전 문제로 독자들이 다이내믹 프로그래밍을 이해했는지 평가할 수 있도록 구성되어 있습니다.
이 책의 첫 번째 챕터는 재귀 호출에 관해 설명하고 있습니다. 재귀에 대한 기본 소개뿐만 아니라, 컴퓨터의 메모리 내부에서 재귀 호출이 어떻게 동작하는지 그림으로 충실하게 설명하고 있습니다. 컴퓨터에 익숙하지 않은 분들에게는 어려울 수 있는 내용이지만, 다이내믹 프로그래밍에 관심을 가질 만한 독자라면 반드시 이해하고 있어야 하는 내용이라고 생각합니다.
두 번째 챕터는 재귀 호출에 대해 조금 더 나아갑니다. 피보나치 수열을 이용하여 재귀와 다이내믹 프로그래밍의 필요성을 언급한 후, 메모이제이션(이 책에서는 메모 전략이라고 함)을 설명하고 있습니다. 이 책에서 소개하는 메모이제이션에 대한 내용은 한 번 읽어봤으면 하는 챕터입니다.
세 번째 챕터부터 다이내믹 프로그래밍의 세계로 들어갑니다. 재귀와 다이내믹 프로그래밍의 차이는 하향식 또는 상향식 접근 방법의 차이인데, 이 내용을 간단하면서도 명확하게 소개하고 있습니다. 일반적으로 상향식 접근 방법으로 문제를 풀이하는 것이 좋은데, 특정 상황에서는 하향식 접근 방법이 유리한 경우도 있습니다. 이런 상황을 설명하고, 실수할 수 있는 부분에 대해 주의사항을 안내합니다.
네 번째 챕터는 다이내믹 프로그래밍의 훈련을 돕기 위해 재미있는 문제들을 제시하고, 문제 풀이를 유도합니다. 이 문제들의 난도는 앞에서 살펴본 것보다는 높은 수준이지만, 지금까지 꼼꼼히 따라왔다면 충분히 풀 수 있는 문제들로 구성되어 있습니다. 직접 풀이해보면 다이내믹 프로그래밍에 한 걸은 다가갈 수 있을 것으로 생각합니다.
마지막 챕터는 다이내믹 프로그래밍에 익숙해지도록 조금 더 어려운 문제들로 구성되어 있습니다. 실제 입사 문제의 난도로 구성된 문제들도 포함되어 실전 테스트라 생각하고 접근하면 좋을 것 같습니다. 만약 풀이하지 못하더라도 꾸준히 연습하고 다양한 방법으로 풀이해보면 큰 도움이 될 것으로 확신합니다.
마치면서
<다이내믹 프로그래밍 완전 정복>은 네 개의 파트와 다섯 개의 챕터, 그리고 두 개의 부록으로 구성(약 220페이지 분량)되어 있습니다. 생각보다 매우 얇은 책이지만, 이 책의 품질은 나쁘지 않습니다. 간단명료하게 잘 설명된 개념 소개로 독자의 이해를 돕고 있으며, 문제를 해결하는 방법을 매력적으로 정리하고 있습니다.
이 책은 프로그래밍에 재미를 붙이고, 다이내믹 프로그래밍에 대해 더 많은 경험을 하고 싶은 분에게 추천하고 싶습니다. 이 책은 재미있는 연습문제를 포함하고 있습니다. 이 문제의 풀이 방법을 생각하면 시간이 흐르는 줄 모르고 문제 풀이를 하는 모습을 발견할 수 있을 것입니다.
마지막으로 이 책은 C 언어를 기준으로 설명하고 있습니다. C 언어를 모르는 독자라면 이 책의 내용을 이해하기 어려울 수 있습니다. 이 책의 역자인 박상은 님은 우수한 번역 품질에 C 언어로 작성된 코드를 파이썬으로 재구현하여 코드를 제공합니다. 비록 파이썬으로 코드를 설명하지는 않지만, 파이썬을 이해하고 있는 독자라면 도움을 받을 수 있을 것입니다. C 언어가 생소한 독자들을 위해 파이썬으로 설명한 책도 출간했으면 하는 개인적인 바람이 있습니다.
사실 알고리즘에 대해서 굉장히 지식이 약했던 나로써 알고리즘 공부를 시작함과 동시에 요즘 추세인 동적프로그래밍이 이 최신 트랜드라는 것을 알고 인터넷으로 공부를 시작 하였는데, 생각보다 인터넷에 나오는 내용 수준 자체가 이미 높은 상태라 받아들이기 힘들었는데 이 책을 보면서 동적프로그래밍이 무엇인지, 다이내막 프로그래밍이 무엇인지 아주 기초부터 원리 동작 방식, 해결방법들을 자세하게 풀어놓은 책이라 동적프로그래밍이 무엇인지 한발짝 나간것 같은 느낌이든다. 사실 이책이 처음부터 쉽게 써져있다고 말 할 수는 없다. 기초적인 프로그래밍 개념이 있어야 하며(C 언어 그러나 아주 기초적인 개념), 최소한의 알고리즘 몇개정도는 알고 있어야 이책을 볼때 거부감 없이 볼 수 있다고 내 개인적인 생각이 많이 든다. 사실 트랜드라 하여 알아보았던 동적프로그래밍이 이책을 보면서 왜 동적 프로그램을 쓰면서, 최적화를 해야 하는지를 알려주고, 문제 해결능력을 향상 시켜준 책이라 책이 약간 얇지만 초심자가 앞으로 동적 프로그래밍을 하기 위해서 또한 면접 준비를 하기 위해서는 이책을 보면서 기초 개념을 세우고 앞으로 공부 방향을 잡아 나간다면 더할 나위 없이 추천할 책이라고 말 하고싶다.
나름대로 꾸준히 알고리즘 문제를 풀기는 하지만, 항상 어려운 부분이 있는데 그 중 하나가 DP, dynamic programming이다. 밀접한 관계에 있는 재귀는 비교적 쉬운데 왜 DP는 항상 어려운지 잘 모르겠는데(아마 노력이 부족해서겠지) 이번에 그걸 보완할만한 책이 있어 읽어보게 되었다. 책을 읽으면서 나름대로 연습을 해서 그런지 읽고 난 후 약간 DP에 대한 자신감이 생기는 느낌이다. 실제 문제를 풀어봐야 확실해지겠지만. 개인적인 연습 코드는 python3로 작성했다.
Chapter 1
완전히 초보자를 위한 재귀에 대한 소개. 재귀 자체에 대한 이해도 필요하지만, 메모리 내부에서 재귀 호출이 어떻게 메모리를 할당하고 해제하는지 컴퓨터 구조의 측면에서 이해하는 부분도 중요하다는 점을 알려준다.
Chapter 2
재귀 호출에 대해 좀 더 설명을 한다. 우선 피보나치 수열과 matrix를 이용해 범위를 줄여 계산하는 종류의 문제가 재귀와 DP에 적합하다는 점을 설명한다. 그 다음으로 메모 전략(memoization)을 설명하는 데 이해하고 사용하기는 쉽지만 이것만으로도 인터뷰에서 꽤 쓸만한 성과를 낼 수 있기 때문에(특히 온라인 문제 풀이의 경우) 혹시라도 몰랐다면 매우 유용한 방법이다.
# p68, 역 사이 최소 비용 구하기 def minCost(cost, s, d): if d == s: return 0 if d - s == 1: return cost[s][d] minRes = cost[s][d] for i in range(s + 1, d): minRes = min(minCost(cost, s, i) + minCost(cost, i, d), minRes) return minRes
Chapter 3
드디어 DP이다. 앞서 살펴봤던 피보나치 수열과 matrix를 이용해 역간 이동 비용을 계산하는 문제를 DP로 해결하면 시간 복잡도가 줄어든다는 걸 설명한다. 그리고 부분 문자열 문제를 이용해 본격적인 설명을 한다. 재귀와 DP의 차이는 하향식이냐 상향식이냐의 차이인데, 이걸 피보나치 수열을 통해 더 자세히 설명한다. 아마 이 부분이 이 책에서 가장 중요하지 않을까 싶은데(최소한 나에게는 그렇다), 재귀와 비슷하면서도 차이가 있는 부분을 인식해야 각각에 알맞은 방법을 찾을 수 있기 때문이다. 마지막으로 드물지만 상향식 프로그래밍(DP)가 하향식에 비해 덜 효율적인 경우에 대해 설명하고 이번 장을 마친다.
# p89, 부분 문자열 다루기 class Solution: # recursive def maxEqualSumLen0(self, s: str) -> int: if s is None or 0 == len(s): return 0def getMaxEqualSumLen(l): m = len(l) // 2 if sum(l[:m]) == sum(l[m:]): return 2 * m return max(getMaxEqualSumLen(l[2:]), getMaxEqualSumLen(l[1:-1]), getMaxEqualSumLen(l[:-2]))l = list(int(c) for c in s) if len(l) % 2 == 0: return getMaxEqualSumLen(l) return max(getMaxEqualSumLen(l[:-1]), getMaxEqualSumLen(l[1:]))
Chapter 4
DP에 익숙해지기 위해 재귀, 메모, DP의 세 가지 방법을 한 가지 문제(2 * 2 matrix에서 최소 비용으로 이동하기)에 대해 설명하고 예제를 소개한다. 이어서 3가지 예제를 통해 DP에 대해 더 설명하는데, 책에도 나와있듯이 실제 면접에서 사용될만한 난이도의 문제들이라 아주 좋은 연습이 된다.
# p105, 행렬에서 최소 이동 비용 구하기 class Solution: def minCost(self, grid: List[List[int]]) -> int: if grid is None or 0 == len(grid) or 0 == len(grid[0]): return 0R, C = len(grid), len(grid[0]) cost = [[0] * C for _ in range(R)] cost[0][0] = grid[0][0] for r in range(1, R): cost[r][0] = cost[r - 1][0] + grid[r][0] for c in range(1, C): cost[0][c] = cost[0][c - 1] + grid[0][c] for r in range(1, R): for c in range(1, C): cost[r][c] = min(cost[r - 1][c], cost[r][c - 1]) + grid[r][c] return cost[-1][-1]# p120, 특정 점수에 도달하는 경우의 수 구하기 class Solution: def countWaysRecur(self, num): if num == 0: return 0def count(n): if 0 == n: return 1 if n < 3: return 0 cnt = 0 for c in [3, 5, 10]: if c <= n: cnt += count(n - c) return cntreturn count(num)def countWaysDP(self, num): if num == 0: return 0dp = [0] * (num + 1) dp[0] = 1 for i in range(1, len(dp)): for c in [3, 5, 10]: if c <= i: dp[i] += dp[i - c] return dp[-1]# p122, 연속된 부분 배열의 최댓값 구하기 class Solution: def maxSubSumArray(self, arr: List[int]) -> int: if arr is None or 0 == len(arr): return 0 if 1 == len(arr): return arr[0] maxSum, subSum = 0, [0] * len(arr) for i, a in enumerate(arr): curSum = subSum[i - 1] + a if curSum <= 0: continue subSum[i] = curSum maxSum = max(maxSum, curSum) return maxSum
Chapter 5
여러가지 문제를 통해 DP에 익숙해지는 연습이다. 문제 풀이 연습 사이트들에서 볼 수 있는, 면접에 나올 가능성이 있는 문제들이다. 개인적으로는 마지막 문제가 가장 기억에 남는데, 수년 전 가고 싶던 회사에서 저 문제를 못 풀어서 떨어졌던 기억이 나기 때문이다. 당시에는 영어 설명부터가 머리에 들어오지 않아 DP 문제라는 생각조차 못했다. 여러 문제 풀이 연습 사이트에서 세부 주제별 문제 분류를 제공하니(i.e. https://leetcode.com/tag/dynamic-programming/) 추가로 연습을 진행하면 더 좋을 것이다.
# p130, 최소 교정 비용 문제 class Solution: def minEditNum(self, s1: str, s2: str) -> int: if (s1 is None or 0 == len(s1)) and (s2 is None or 0 == len(s2)): return 0 if s1 is None or 0 == len(s1): return len(s2) if s2 is None or 0 == len(s2): return len(s1)R, C = len(s1), len(s2) grid = [[0] * (C + 1) for _ in range(R + 1)] for r in range(1, R + 1): for c in range(1, C + 1): if s1[r - 1] == s2[c - 1]: grid[r][c] = 1 + grid[r - 1][c - 1] else: grid[r][c] = max(grid[r - 1][c], grid[r][c - 1]) return max(R, C) - grid[-1][-1]# p152, 부분집합의 합 구하기 class Solution: def minEditNum(self, s1: str, s2: str) -> int: if (s1 is None or 0 == len(s1)) and (s2 is None or 0 == len(s2)): return 0 if s1 is None or 0 == len(s1): return len(s2) if s2 is None or 0 == len(s2): return len(s1)R, C = len(s1), len(s2) grid = [[0] * (C + 1) for _ in range(R + 1)] for r in range(1, R + 1): for c in range(1, C + 1): if s1[r - 1] == s2[c - 1]: grid[r][c] = 1 + grid[r - 1][c - 1] else: grid[r][c] = max(grid[r - 1][c], grid[r][c - 1]) return max(R, C) - grid[-1][-1]# p171, 거스름돈 최적화 class Solution: def minCoins(self, coins: List[int], money: int) -> int: if coins is None or 0 == len(coins): return 0dp = [float('inf')] * (money + 1) dp[0] = 0 for m in range(1, money + 1): for coin in coins: if m < coin: continue elif m == coin: dp[m] = 1 else: if dp[m - coin] > 0: dp[m] = min(dp[m], 1 + dp[m - coin]) return dp[-1]# p176, 철근 자르기 class Solution: def maxProfitRecur(self, costs: List[int], length: int) -> int: if costs is None or 0 == len(costs): return 0def getMaxProfit(acc, _costs, _length): if _length == 0: return acc if _length < 0: return 0 subProfit = 0 for rodLen, cost in _costs: if rodLen > _length: continue acc += cost curProfit = getMaxProfit(acc, _costs, _length - rodLen) subProfit = max(subProfit, curProfit) acc -= cost return subProfitreturn getMaxProfit(0, [(i + 1, cost) for i, cost in enumerate(costs)], length)def maxProfit(self, costs: List[int], length: int) -> int: if costs is None or 0 == len(costs): return 0dp = [[0, 0]] * (length + 1) dp[0] = [0, 0] for d in range(1, length + 1): for i, cost in enumerate(costs): rodLen = i + 1 if d < rodLen: continue candCost = dp[d - rodLen][1] + cost if dp[d][1] < candCost: dp[d] = [dp[d - rodLen][0] + 1, candCost] return dp[-1][1]# p187, 최장 회문 부분 수열의 길이 class Solution: def maxPalindromeLen(self, s: str) -> int: if s is None or 0 == len(s): return 0R = C = len(s) rStr, grid = s[::-1], [[0] * (C + 1) for _ in range(R + 1)] for r in range(1, R + 1): for c in range(1, C + 1): if s[c - 1] == rStr[r - 1]: grid[r][c] = 1 + grid[r - 1][c - 1] else: grid[r][c] = max(grid[r - 1][c], grid[r][c - 1]) return grid[-1][-1]
한국어판 부록 A
알고리즘 서적에는 항상 빠지지 않는 시간/공간 복잡도에 대해 간단히 소개한다. 간단한 소개에 그치기 때문에 자세한 내용은 자료구조/알고리즘 교과서를 보는 게 좋다
한국어판 부록 B
codility 사용 방법을 소개한다. 많은 회사들이 면접 시 1차로 리크루터와 통화를 한 후 두 번째 단계로 이런 문제 풀이 사이트에서 문제를 풀고 제출하게 하는데, codility나 hackerrank가 가장 유명한 편이다. 우리나라에서도 점점 많은 회사들이 도입하고 있기 때문에 시간 날 때마다 풀어보면서 익숙해지는 게 좋다.
다이내믹 프로그래밍은 흔히 [동적 계획법]이라고 변역하는 알고리즘 접근 방법론이다. 개발 방법론은 아니다. 문제 풀이 방식에 가깝다. 다이내믹 프로그래밍은 하위 문제를 한 번만 계산하는 상향식 문제 풀이 접근법이다. 따라서 직관적인 재귀 호출보다는 이해하기가 상대적으로 어려운 경우가 많다.
[대상 독자]
코딩 면접을 앞두고 있는 개발자나 알고리즘 대회 참가를 앞두고 있는 학생을 위한 책이다.
[구성]
책은 세로 길이가 손바닥을 편친 것만할 정도로 자그마하며, 총 페이지가 220페이지 정도로 아주 얇다. 내용은 재귀 호출의 이해부터 시작하여, 다이내믹 프로그래밍의 이해, 적용 전략, 실전 문제 순으로 구성되어 있다. 다이내믹 프로그램에 빠르게 익숙해지기를 원하는 사람들을 위한 구성이다. 앞에서는 보다 단순한 개념 위주로 설명을 시작하지만, 뒤로 갈수록 페이지를 넘기는 것이 점점 더 어려워진다. 난이도가 올라갈수록 멈추고 생각해야하는 지점이 늘어나기 때문이다.
[장점]
무엇보다 좋았던 점은 번역의 정확도와 자연스럽게 읽히는 한글 문장의 완성도이다. 그리고 시간 복잡도와 공간 복잡도라는 개념을 이해하지 못하는 초보자들을 위해서, 원서에 없는 기본적인 내용을 먼저 읽어볼 수 있도록 부록에 추가한 점이 좋았다. 또한 책 구성도 하나의 주제에 잘 집중해서 체계적으로 설명을 진행해나간다는 점이 눈에 띈다.
[단점]
C언어로 씌여진 책이다. 출판사의 깃허브(http://github.com/crapas/dp)에서 파이썬으로 된 코드도 제공하기는 하나, 본문의 설명은 오직 C언어 기준으로만 적혀 있기에, C언어의 기본 문법과 포인터, 메모리, 성능에 대한 기본적인 이해가 있지 않다면 제대로 이해하기가 어려울 것 같다.
[후기]
업계에 발을 오래 담그고 있음에도 전통적인 프로그래밍, 그 중에서도 면접 대비용 알고리즘 책은 오랜만에 보는 느낌이다. 그래도 다이내믹 프로그래밍에 대한 기본적인 개념들을 이해하고 정리하기에는 좋았다. 맨 뒤 챕터의 문제까지는 다 못풀었지만 말이다. 내 분야가 코드 자체의 성능보다는 외부 요인이 더 많은 분야라서, 더 효율적으로 코드를 작성하기 위해서 꼭 필요한 지식을 너무 잊어버린게 아닌가 약간의 반성도 가져다 준 책이다.
순전히 책 표지에 끌렸다. 물론 책이 매우 얇은 점도 한 몫했다. 책 표지에서 알 수 있듯이 이 책은 재귀와 관련된 내용을 주로 다룬다.
2
책이 크게 4파트로 나뉘는데, 파트1과 파트2는 재귀호출에 대한 기본적인 내용(기본적이라고 말했지만, 사실 재귀에 필요한 거의 대부분의 내용을 담고 있음) 책 제목에 적혀 있는 다이내믹 프로그래밍에 필요한 접근방식(상향/하향)에 대해서 진자세히 다루고 있다. 책을 읽다보면 예제로 행렬에 관련된 내용을 다루고 있어서 뭐랄까… 약간의 어색함이 있지만 여튼, 파트1/2만 잘 넘겨도 충분히 많은 것을 알 수 있다. 파트1/2는 재귀에 대해서 피상적으로 알고 있던 내용을 일목요연하게 정리해주는 파트라 2~3번 정도 읽었다. 하향식/상향식 접근의 경우 내가 할 수 있다고 믿었던 것과 실제 코드를 작성하는 사이의 괴리를 어느 정도 느낄 수 있을 만큼 예제가 잘 정리되어 있으니 꼭 참고하자.
3
파트3/4로 진입하면 연습문제의 난이도가 약간 높아진다. 실전 문제를 풀면서 실력을 향상 시키기 위한 목적으로 다양한 문제를 제공하고 있다. 파트4의 경우 알고리즘의 세부적인 내용들에 대해서 다루고 있어서 파트3/4 정도를 쉽게 읽을 수 있다면 굉장한 실력이라 할 수 있다. 문제를 잘 이해하고, 파트2에서 배웠던 내용을 복습하면서 차근 차근 문제를 풀어보고 좋겠지만(하하!) 생각만큼 잘 안되니, 2~3번 정도 연습해보자.
4
파트1/2 수준의 경우 일반적인 개발자나 학습자는 대부분 알고 있는 경우가 많고, 파트3/4의 경우 난이도가 있기 때문에 주변 동료나 친구들과 함께 문제를 풀어볼만하다. 특히 컴고 2~3학년 학생에 권한다. 재귀는 한 번 잘 배워두면 평생 써먹을 수 있으니! 시간날 때 열심히 연습하자.
프로그래머 혹은 컴퓨터 공학도라면 누구나 이 무서운 단어들을 들어봤을 것이다. 대부분의 프로그래머는 이런 용어가 세상에 존재하는구나 하는 정도로 넘어가고 잊어버린다. 이 단어들은 프로그래머에게 왜 무서운 단어가 되었을까? 먼저, 본 도서의 장점을 전달하기 위해 필자가 겪었던 다이내믹 프로그래밍 경험을 말씀드리고자 한다.
이름부터가 직관적이지 않다. 본 도서 서문 “옮긴이의 말”에서 역자는 Dynamic Programming을 “동적계획법”이 아닌 “다이내믹 프로그래밍”으로 음차하겠다고 소개한다. 자칫 독자가 프로그래밍 방법론으로 혼동할 수 있기 때문이다. 역자가 우려하듯 우리말 번역과정에서 진의가 꽤 소실된다.
리처드 벨만은 그의 자서전, “태풍의 눈”에서 Dynamic Programming의 어원을 다음과 같이 설명한다.
‘의사 결정 프로세스’라는 이름을 사용했지만, 여기에서 ‘프로세스(Process)’라는 단어를 사용하는데 여러가지 차질이 생겨버리고 만 것이다. 그래서 나는 사람들이 알지 못하게 ‘계획법(Programming)’이라는 단어를 붙였다. 또한 나는 이 프로세스가 다단계로 이루어져 있으며, 시가변적(time-varing)이며, ‘동적(Dynamic)’이다라는 개념(idea)이 전달되길 원했다. 이 단어야말로 내가 연구하는 알고리즘의 성질을 정확하게 짚어내었고, 게다가 윌슨에게도 피해를 입히지 않으며 공군도 이 단어에선 꼬투리를 잡지 못했으니 그야말로 일석이조의 효과를 누린 것이다.
벨만이 처한 상황에는 당시 모종의 정치적인(?) 이유가(상급자, 연구비 등) 개입되며 직관성이 흐려진 듯 하다. 그래서 필자는 대다수의 해석에 따라 다음과 같은 뉘앙스로 이해한다.
다이나믹(Dynamic) : 동적 메모리(시간에 따라 변하는 메모리)
프로그래밍(Programming) : 다단계(큰 문제 안에 작은 문제들이 중첩된)로 이루어진 문제 풀이계획
결론 : 시간에 따라 변하는 데이터를 고려하여, 큰 문제를 작은 문제로 쪼개서 푸는 방식
실무에서 좀처럼 쓰이지 않는다.
여러분은 지금까지 재귀 혹은 다이내믹 프로그래밍을 몇번이나 활용하셨는지?
필자 역시 대학원 혹은 취업 면접이 있을때만 책으로 접했고, 실무에서 사용한 경험은 많지 않다. 가장 쉬운 경험을 예로 들자면 즐겨찾기 관리를 위한 App을 개발하면서 즐겨찾기 폴더를 순회하여 폴더별 저장된 URL을 가져오는 용도로 활용한 적이 있다.
시간복잡도와 찰떡궁합이다. 위에서 언급한 즐겨찾기 관리 App의 경우를 보자. 테스트를 진행하며 폴더 Depth를 100으로 늘렸더니 생각외로 꽤 오랜 수행시간이 소모되었다. 재귀함수를 이용하여 매우 소량의 코드로 문제를 해결한데다 기억이 가물가물한 재귀를 제법 빠르게 구현했기에 나름 속으로 ‘아직 살아있구만!’라고 자화자찬하던 와중에 약간 충격을 받았다.
다른 관련코드들 역시 시간을 잡아먹을만한 부분이 보이지 않아서 결국 알고리즘 책을 간만에 펼쳤다. 문제는 의외로 간단했다. 재귀 함수의 시간복잡도가 지수시간을 잡아먹고 있었던 것이다. 알고리즘의 기초 내공의 중요함을 다시금 깨닫게 된 순간이었다.
메모리 구조와 밀접한 관련이 있다.(공간복잡도) 경력 2년차 초보때 벌어진 일이라 혼자만의 추측이 시작되었다. “결국 재귀를 버려야 하나..? 이래서 사람들이 재귀를 안쓰는 거구만..!”등등…결국 Loop를 이용해서 다시 구현할까 생각했는데 왠지 지는 느낌이 들어 싫었다. 결국 다시 알고리즘 책을 펴보았다. 역시나 선배들이 해결해 온 역사를 통해 힌트를 얻을 수 있었는데 메모이제이션(Memoization)라는 캐시 기능을 활용하여 재귀 함수가 호출될 때 시간복잡도를 O(N)으로 줄일 수 있었다. 배열 하나 썼을뿐인데 이렇게 속도가 빨라지다니! 조금 더 흥미가 생기기 시작했다.
메모리 구조를 분석하며 얻은 또 하나의 수확은 Stack 시각화를 통한 개념 명확화였다. 메모리 및 스택을 그림으로 그리고 활성레코드 함수 변화를 정리해보니 어렴풋했던 재귀 호출의 동작방식이 명확하게 이해되는 것이었다. 당시 정립한 개념 덕분에 지금도 DP를 활용하여 개발할 때 머리 속 스택그림의 도움을 많이 받는다.
일상속의 직관과 거리가 멀어 전략이 필요하다. 꼬리에 꼬리를 끝없이 물어가는 재귀 호출을 구현 시 명확한 기준이 없다면 재귀적 사고의 악순환(?)이라는 주화입마에 빠지고 만다. 머리가 복잡해지면서 뇌는 본능적으로 재귀를 피하려고 한다. 따라서 가장 중요한 것은 뇌에게 탈출구를 안내할 수 있는 종료조건과 작은 문제에 대한 명확한 정의이다.
재귀가 보통 Top-Down 방식을 이용하는 것과 달리(Top-Down 방식은 이름에서 유추할 수 있듯이 보다 큰 인자에서 작은 인자로의 재귀 호출을 반복한다. 따라서 동일한 인자를 가지는 함수가 매번 수행되어 성능상 치명적인 약점을 가지게 된다. 대신 코드의 가독성이 높다.) DP에서는 Bottom-Up방식을 이용한다.
재귀에 비해 크게 어려울 것이 없는것이 함수대신 변수(배열 등)의 이미 연산된 작은 값들을 활용하여 큰 값들을 반복적으로 채워나가는 방식이다. 덕분에 동일값에 대한 연산을 피하여 성능을 높일 수 있는 장점이 있다. 재귀와 마찬가지로 DP를 적용할 수 있는 문제인지 어떻게 세부적으로 구현할 지 등에 대한 전략이 존재한다.
면접과 실무를 넘어서서… DP 자체를 명확히 이해하는 것도 중요하지만 공학분야에 있어서만큼은 언제, 어디에 적용할 수 있는지를 아는 것이 더 중요하다. (참고 : WHAT « WHEN & WHERE) DP는 언제 어디에 적용할 수 있을까?
부분적으로는 O(n^3) 등 다항식 수준의 시간복잡도를 O(n*logn) 등의 로그 수준으로 줄여 성능을 높일경우 DP를 활용할 수 있을지 판단해야 한다.
더불어 한단계 수준을 넘어선 전혀 다른 영역에의 응용이 가능하다. 예를들면 강화학습이 있다.
강화학습은 각 Step별 Action을 취하는 문제를 모델이 없는(Model-free)상태에서 MDP(Markov Decision Process)를 활용하여 풀어나가는 방법이다. 때문에 Model의 Environment에 해당하는 Reward, State Transition Probability등을 최적화하기 위해 Learning(학습)을 해 나간다.
DP와의 접점이 느껴지시지 않는지?
DP는 Model을 완벽히 안다는 전제하에(Model-based) Bellman Equation을 풀어 Environment를 구하는 방식이다. 그래서 Planning이라고 부르며 이를 보완하여 Learning을 통해 Environment를 최적의 상태로 찾아가는 것 즉, 강화학습 알고리즘을 만들게 된 것이다. 때문에 DP의 개념 및 활용방안을 정확히 모른다면 강화학습에 대한 이해는 물론이고 보다 나은 방법을 찾기가 거의 불가능할 것이다.
더불어 문자열 연산을 다루는 NLP에 있어서도 DP의 문제 해결방식은 큰 도움을 준다.
DP에 대해 더 설명하고 싶지만 필자의 짧은 지식으로는 여기까지다. 하지만 경제학 등 DP의 활용도는 무궁무진할 것이고 어떻게 다른 지식과 융합, 보완하느냐에 따라 멋진 걸작이 나올지도 모른다. 필자가 경험한 이 일련의 과정에 비추어 본 도서가 어떤 장점을 갖는지 다음장에서 간단히 다뤄보고자 한다.
다이내믹 프로그래밍을 위한 본 도서의 장점
앞장에서 다이내믹 프로그래밍 경험 및 스스로 학습해왔던 과정을 간략하게 설명하였지만, 사실 그 간략함이 몇 년간 다이내믹 프로그래밍과 관련하여 학습한 지식의 거의 전부이다.
본 도서를 읽으며 놀라웠던 점은 필자가 겪었던 시행착오나 전략이 고스란히 담겨있다는 것이다. 필자의 지식이 고수들에 비할바 못하는것을 알면서도 꼭 이런 양서를 만나면 나만알고 있었을 듯한 밑천이 외부에 다 털린 느낌이 들어 배가 아프다. 하수라서 그런것일까?
다이내믹 프로그래밍 자체를 적용하기 위해 몇일간 고민했던 흔적은 아이러니하게도 자연어로 정리하면 고작 한줄 정도 담긴다. 즉, 다이내믹 프로그래밍을 자연어로 정리하면 설명력이 크게 떨어진다. 미묘한 기법과 뉘앙스를 전달하기 위한 사고과정에 대한 뚜렷한 설명이 거의 불가능하다는 것이다.
때문에 본 도서 또한 전략과 이론에 관련된 내용이 매우 짧다. 거의 대부분의 페이지는 예제와 예제의 설명, 시각적 설명이 차지하고 있다. 많은 예제를 바탕으로 사고과정을 공유하는 것이 거의 유일한 해결책이라는 생각이 드는데 본 도서가 그런 접근법을 통해 다이내믹 프로그래밍 예제를 같이 풀어보고 알기쉽게 설명해줌으로써 주화입마에 빠질 우려를 줄여준다.
명쾌한 전략제시 앞서 설명한 바와 같이 자연어로 다이내믹 프로그래밍이라는 문제풀이 접근방식을 설명하긴 보통 어려운 일이 아니다. 대신 기억하기 쉬운 핵심 전략을 머리속에 두고 접근하는 것과 대책없이 프로그래밍을 시작하는 것은 큰 차이가 있다. 아래 그림은 다이내믹 프로그래밍과 메모이제이션 그리고 재귀 호출에 대한 핵심 전략을 기술한 페이지이다.
사고과정의 이해를 돕는 시각화 다이내믹 프로그래밍은 예제와 실전을 통한 사고과정의 고민의 깊이가 어느 정도인지에 따라 그 활용 능력이 갈린다. 사고과정이 일상의 직관과는 동떨어져있어 쉽게 포기하기 쉬운데 절대 포기하지 않도록 저자, 역자의 고민의 흔적이 설명에 녹아있다. 더불어 아래 그림과 같이 직관적인 이해를 돕는 시각화를 통해 이해도를 크게 높여준다.
원리를 바탕으로 한 전달력, 중간중간 깨알같은 선수지식의 소개 기저에 숨어있는 원리를 설명하지 않고 소스코드의 주석과 결과만으로는 다이내믹의 정수를 얻기 힘들다. 기본 원리를 절대 놓치지 않으려는 시도가 이 서적의 또 다른 매력이다.
예를들면 다이내믹 프로그래밍이 가지는 장점을 소개하기 위해, 또 이해도를 높이기 위해 메모리 구조를 설명한다. 이를 통해 공간복잡도의 계산이 훨씬 쉬워지고 다이내믹 프로그래밍이 얻게되는 시간, 공간복잡도 성능향상이 어느정도인지 개념적으로 와 닿도록 도와준다.
아래 그림은 메모리 구조 및 스택영역에서의 재귀함수의 활성레코드를 보여줌으로써 머리속에 스택의 동작방식을 이해하고 있는것이 얼마나 다이내믹 프로그래밍에 대한 이해도를 높여주는지 알 수 있게 해준다.
다이내믹 프로그래밍과 관련된 거의 모든 예제 본 도서에 소개된 재귀 및 다이내믹 프로그래밍의 관련 예제는 무려 20개가 넘는다. 그 정도면 거의 왠만한 실무를 커버할 수 있는 수준이 아닌가 싶다. 제대로 이해를 못했다면 예제의 감각이라도 충분히 잡아 반드시 활용할 수 있게 해주려는 저자의 의지가 돋보인다.
아래 그림은 필자가 재미있게 풀어본 예제인 “문자열 인터리빙 확인” 문제인데 사고과정을 명확하게 시각화하여 이해를 돕는다.
더불어 아래 “거스름돈 최적화” 문제와 같이 DP와 유사한 탐욕 알고리즘과의 비교도 시도한다. 탐욕 알고리즘이 반드시 최적해가 아닌 케이스를 설명하며 비교 과정을 통해 DP 특성에 대한 이해를 더욱 높여준다.
본 도서의 모든 소스코드는 C와 Python 두종류의 언어로 제공된다. 두 언어를 모두 활용한다면 보다 이해도를 높일 수 있다.
이 책은 크게 세부분으로 구성되며, 각 파트에서 다루는 내용을 아래와 같이 요약해 보았다.
1. 재귀호출과 메모리, 활용전략(Part1)
재귀 접근전략, 재귀 호출과 메모리
최적의 하위구조, 하위 문제의 반복 계산, 메모이제이션(메모전략)
예제 : sum(n), 점화식, 하노이탑, 피보나치, 역사이 최소 비용 등
2. 다이내믹 프로그래밍(Part2)
Top-Down 및 Bottom-Up 접근방식의 차이
다이내믹 프로그래밍의 적용을 위한 전략
예제 : 부분 문자열, 계승함수, 이진트리, 행렬 최소이동비용, 타일공터 채우기, 경우의수, 연속부분 배열의 최댓값 등
3. 실전연습(Part3)
최소교정비용문제, 직사각형의 총 경로수, 문자열 인터리빙, 부분집합의 합
최장공통부분수열, 거스름돈 최적화, 철근자르기, 0 -1 배낭, 최장회문부분수열, 달결낙하퍼즐 등
부록 : 시간 및 공간복잡도, 코딜리티(온라인 코딩 테스트) 활용법
요약하며…
다이내믹 프로그래밍이 어려운 가장 큰 이유는 일반적인 직관과는 다른 사고방식을 필요로 한다는 점이다. 특히 사고과정을 면대면이 아닌 책으로 기술한다는 것은 더욱 어려운 일일 것이다.
이런 어려움을 해결하고자 본 도서는 명확한 전략, 사고과정에 대한 깊은 설명, 시각화를 이용한 사고과정의 보조, 원리를 중시한 핵심 개념 설명을 활용하여 DP에 대한 이해도를 극대화 시켜준다. 왜 이 책이 실리콘밸리의 우수한 IT인력을 공급하는 인도 그리고 해외 시장에서 베스트 셀러에 올랐는지 알 수 있는 부분이다.
아쉬운 점이 하나 있다면 독자로 하여금 DP에 대한 이해를 포기하지 않도록 책 중간중간에 선수 지식이 종종 소개되는데 어느정도 내공이 찬 프로그래머라면 재귀 및 DP에만 집중하기에 약간 산만한 느낌을 받을 수 있겠다는 생각이 들었다. 하지만 초중급자를 위해서는 이만큼 친절할 수가 없다.
아울러 C, Python 두가지 언어로 예제를 작성한 바 포인터의 유무, 객체지향의 유무 등 언어 특성에 따라 가려지기 쉬운 DP의 개념을 두 언어로 구현, 비교해봄으로써 이해를 명확하게 할 수 있다는 장점이 있다. 더불어 두 언어 자체에 대한 이해도가 높아지는 것은 보너스다.
예쁜 색상으로 디자인되고 무겁지 않아 들고 다니면 왠지 뿌듯한 감성이 충만된다. 강화학습 또는 NLP를 학습하며 DP의 명확한 개념을 잡고 싶은 분, 알고리즘 코딩 테스트를 앞둔 분, DP를 뽀개 완전히 두려움을 없애고 싶은 분께 꼭 일독을 권한다.
<한빛미디어 출판사>
믿고보는 “한빛미디어 출판사”. IT분야에서 독보적인 양질의 도서를 출판하는 회사입니다. “나는 프로그래머다” 팟캐스트 후원, DevGround2019 행사, 리뷰어 모집, 다양한 학습 지원 등 다양한 분야에서 사회에 공헌하는 개발자와 공생하는 업체입니다. IT분야에 관심 있으시다면 한빛미디어의 책으로 후회없는 출발을 하실 수 있습니다.
책의 두께도 얇아 어디서든 가볍게 읽을 수 있으며 코딩 테스트를 앞둔 사람에게, DP 문제가 약한 분들에게 추천드립니다.왜 DP 로 문제를 풀어야하는지 상향식 하양식 방식은 어떤 경우에 다르게 풀어야 하는지에 대하여 잘 나와있습니다.막연하게 재귀로 풀면 좋다가 아니라, 재귀로 풀면 프로세스나 메모리 구조로 이런 점이 더 좋다는 점을 알 수 있어서 더 이해하기 쉬웠던것 같습니다.
개발자로 취업을 하려면 코딩면접을 봐야 한다. 운이 좋게 자주 나오는 알고리즘 문제를 외워서 나오면 다행이지만 새로운 유형이 나오면 멘붕이 올것이다. 이책은 알고리즘 공부 어려움 점을 쉽게 해결 할수 있는 다이내믹 프로그래밍을 배울수 있다. 재귀호출,메모전략, 상향식 다이내믹 프로그래밍의 개념을 자세히 설명하고 단골로 출제되는 알고리즘 문제부터 인터뷰 문제까지 다양한 예제에 적용을 하고 있다. 외워서 알고리즘을 푸는 것이 아니라 알고리즘적 생각 다이내믹 프로그래밍을 이해하고, 문제 풀이에 적용할수 있는 능력을 배울수 있을 것입니다.
