메뉴 바로가기 검색 및 카테고리 바로가기 본문 바로가기

한빛출판네트워크

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

빠르고 우아한 상향식 문제 풀이법

한빛미디어

번역서

판매중

  • 저자 : 미나크시 , 카말 라와트
  • 번역 : 박상은
  • 출간 : 2019-10-04
  • 페이지 : 220 쪽
  • ISBN : 9791162242063
  • 물류코드 :10206
  • 초급 초중급 중급 중고급 고급
4.7점 (24명)
좋아요 : 11

빠르고 우아한 상향식 문제 풀이법으로 

코딩 면접 광탈에서 멘탈갑으로 거듭나기 

 

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

 

 

주요 내용

  • 재귀 호출의 A to Z
  • 재귀 호출과 메모리 구조의 관계
  • 최적의 하위 구조 + 하위 문제의 반복 계산
  • 메모 전략을 활용한 재귀 호출 성능 개선
  • 하향식 접근 vs 상향식 접근
  • 다이내믹 프로그래밍 기초부터 문제 풀이 전략까지
  • 부분집합의 합, 최장 공통 부분 수열, 0-1 배낭, 회문 등 실전 문제 풀이

 

 

700_all_2_thicker_border.jpg

 

미나크시 저자

미나크시

코딩 인터뷰 전문 스타트업 리탐바라 테크놀로지(www.ritambhara.in)의 공동설립자. 컴퓨터사이언스 석사 학위가 있으며 기술 스타트업 창업가, 공인 요가 트레이너, 두 아이의 엄마 등 역할이 많지만 워라밸을 잘 유지하고 있다. 말하자면 삶 속에서 문제 풀이와 최적화를 실천하고 있다.

카말 라와트 저자

카말 라와트

소프트웨어 개발자이자 교육자, 저술가, 사업가. 다양한 분야와 플랫폼에 걸쳐 대규모 데스크톱, 클라우드, 모바일 애플리케이션의 전체 수명주기를 구현한 경력이 있다. MS 원노트, 어도비 포토샵, 삼성 갤럭시 커넥트 등 난도가 높은 프로젝트의 기술 아키텍트를 역임했다. MS, 어도비 및 많은 스타트업에서 핵심 인터뷰어를 맡기도 했다. MS에서 시니어 SDE로 근무하다 2006년부터 학생들에게 프로그래밍 인터뷰 돌파법을 코칭하고 있다.

박상은 역자

박상은

컴퓨터에 붙은 그림을 보고 애플이라는 단어의 뜻을 알게 된 이 땅의 흔한 개발자다. 포항공과대학교에서 전산학을, 한국과학기술원에서 인공지능을 공부한 덕분에 알파고와 스카이넷을 구분할 줄 아는 지혜를 갖추게 되었다. 메일, 브라우저, CMS, 도서 관리 시스템 등 일관성 없이 다양한 프로젝트에 참여했다. 이렇게 하여 물에 물 탄 듯한 경력이 완성되는 듯했으나, 최근 몇 년은 빅데이터 처리 관련 연구 개발에 집중했다. 현재 인공지능연구원의 Field AI팀 팀장으로 딥러닝을 활용해서 개인과 기업에 도움이 되는 서비스를 개발하고 있다. 특히 자연어 데이터와 금융 데이터를 딥러닝과 빅데이터 기술을 활용하여 분석하는 문제를 고민 중이다.

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

 

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

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

 

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

 

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

 

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

 

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

 

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

 

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

 

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

요즘 가장 각광받고 있는 업종 중 하나가 바로 프로그래밍 분야일 것이다.
프로그램을 통해 새로운 것을 만들어 내는 기쁨은 예술가의 그것과 다르지 않을 것이다.
문제는 책을 통해 컴퓨터 언어만을 공부하면 누구나 프로그래머가 되는 것은 아니라는 것이다.
초보자는 책을 통해 배운 내용만으로도 충분할 수 있으나 어느 단계를 넘어가기 시작하면 어려움에 봉착한다.
컴퓨터 전공자들이 기본적으로 배우는 '자료구조'와 '알고리즘'이 바로 그 벽이다.
 
이 책 '다이내믹 프로그래밍 완전 정복'은 이 중 '알고리즘'의 최적화와 해결방안을 알려주는 책이다.
 

dynamic.jpg

 

 
흔히 동적 계획법이라고도 하는 것으로 프로그래머로써 레벨업을 위해 반드시 넘어야 하는 것이다.
프로그램을 전문적으로 하는 큰 회사에 입사하기 위해서는 코딩 테스트를 위해 꼭 알아야 하는 것이기도 하다.
프로그램에는 정답이 없다.
시스템 특성에 따라, 언어에 따라, 심지어 환경에 따라 답이 달라질 수 있다.
 
우리가 다이내믹 프로그래밍을 알아야 하는 이유는 알고리즘을 통해 코딩의 질을 높이고 단순화할 수 있기 때문이다.
책의 시작은 '재귀 호출'로 시작하고 있다.
재귀야 말로 알고리즘의 효용성을 극대화하고, 프로그래머의 실력을 검증할 수 있는 좋은 코딩 테스트 중 하나이다.
특정 프로그래밍 언어에 대한 숙련도가 아니라 해당 문제의 논리적 이해도와 창의적 해결방법을 확인할 수 있다.
그 다음으로 '다이내믹 프로그래밍'을 보여주고 있다.
상향식 프로그래밍이 무엇인지, 언제, 어떻게 사용하는지, 그리고 언제 사용하면 안되는지 등 다이내믹 프로그래밍의 모든 것을 보여주고 있다.
 
마지막의 실전 문제는.... 솔직히, 아직 모두 풀어보지 못했다.
앞서 말한 바와 같이 다이내믹 프로그래밍은 언어의 숙련도와 상관없이 알고리즘에 대한 깊은 이해가 있어야 한다.
알고리즘은 당연히 수학적 지식을 바탕으로 한다.
주변의 개발자들 중 더 나은 알고리즘을 만들기 위해 고등학생때 보았던 수학 책을 다시 펼치는 분들도 있다.
 
대부분 알고리즘의 책들이 자바나 C로 설명하고 있는데 이 책은 파이썬 소스를 제공하고 있다는 것이 마음에 들었다.
원본은 C 소스만 제공하고 있으나, 출판사에서 번역을 하면서 파이썬 코드를 별도로 제공하고 있다.
솔직히 이것이 내가 이 책을 보게 된 이유 중 하나이기도 하다.
 

content.jpg

 

 
책 뒷 표지이다.
이 책에서 주로 다루고 있는 내용을 보여준다.
여기서 내 눈길을 확 잡아 끈 문장이 있다.
"다이내믹 프로그래밍의 장벽을 넘지 못해 컴공과에 가지 못하고 출판사에 들어간 기획자가 혼신을 다해 야근하며 편집했다."
요즘은 개발자들도 많이 하지 않는 야근을 하며 만들었다니 더 애잔하다.
그래서인지 이 책의 편집이 너무나 마음에 들고 하나하나에 더 애정이 간다.
이 자리를 빌어 편집자 분에게 좋은 책을 만들어 준 감사의 말씀을 전하고 싶다.

옆구리 혹은 가방안의 알고리즘 문제 풀이 책에서 절대 빠지지 않는 부분이 다이나믹 프로그래밍 부분인데  
알고리즘 문제 풀이에서 절대 빠질수 없는 부분이니 만큼 설명도 방대하고 예제들 또한 이해하기도 어렵다. 

이 책은 다이나믹 프로그래밍 부분을 아예 따로 뽑아내 설명을 하고 있다. 
여러 유형의 문제에 대해 다양한 방법을 설명하는 다른 책들과는 달리 
다이나믹 프로그래밍에 한가지 방법에 대해 쉽고 명확한 설명을 목표로 한다. 
책도 생각보다 얇으며 책의 문체가 편해 책을 읽기에도 부담이 적다. 


많은 회사들이 S/W 개발자를 필요로 하면서 그에 함께 정확한 역량 측정을 위한 지표로써 알고리즘 문제 풀이를 활용한다. 
알고리즘 문제 풀이와 개발 역량과의 직접적인 관계가 있는지는 잘모르겠으나  
구직을 준비하는 사람들에 입장에서는 무시할 수 없는 것이 사실이다. 

프로그래밍의 많은 세부 분야 중 알고리즘 보다 다른 영역에서 더 흥미를 느끼고 역량이 드러날수 있음에도 불구하고 
역량 평가의 지표로써 활용되기에 어떤 식으로든 어느정도의 지식을 습득하고 시험에 대비해야 하는 것이 현실이다. 

때론 의사와는 무관하게 하고 싶은 것을 하는 것이 아니라 해야 해서 하는 상황이 들이 닥치기도 하지만  
때론 의사와는 무관하게 우연히 새로운 지식을 접하고 새로운 즐거움을 알게 되는 계기가 되기도 한다. 

부디 새로운 지식을 접하고 새로운 즐거움을 알게 되는 계기가 되었으면 좋겠다. 

 

IMG_4671.jpg

 

안녕하세요, 괴짜 개발자 namedboy 입니다.

 

book_cover_2019_12_15.jpg

나는 다이내믹 프로그래밍이 정확히 무엇을 의미하는지 전혀 알지 못하는 상태였기 때문에 약간의 부담감을 안고 책을 읽기 시작했는데, 그런 나에게 이 책은 다이내믹 프로그래밍이 무엇인지에 대해서 맛볼 수 있는 중요한 기회를 선사해주었다.

일단 책의 처음은 재귀에 대한 내용으로 시작한다. 재귀의 경우 꽤나 자주 접했기에 비교적 쉽게 이해할 수 있었다. 책의 내용 중에서 재귀를 사용할 때 주의해야할 것에 대해서 아래와 같이 나와있었다.

  1. 재귀에는 항상 종료 조건이 있어야 한다. 종료 조건이 없으면 재귀 호출이 무한히 반복된다.
  2. 재귀 함수는 전체 작업의 일부만 수행하고 나머지는 재귀 호출에 위임한다.

어찌보면 너무나 당연한 이야기였지만, 너무나 당연하기 때문에 간과할 수 있는 부분에 대해서 명확하게 짚어주고 있었다.

또한 재귀에 대해 설명하면서 아래와 같은 말도 덧붙이고 있었다.

쉬운 코드와 복잡한 코드 중에 선택해야 한다면, 성능이나 메모리의 이점이 있지 않은 한 쉬운 코드가 좋습니다.

같은 문제를 비슷한 노력으로 해결할 수 있다면 재귀 호출을 사용하지 않는 쪽으로 구현하는 것이 바람직합니다. 만들어진 프로그램을 실행하보면 재귀 호출을 사용하지 않는 경우가 실행도 빠르고 필요한 메모리의 양도 작습니다.

깊이 공감한다. 정말 명확한 이유가 있지 않은 한 재귀 호출을 남발하는 것은 좋지 않다고 생각한다. 물론 재귀 호출로 문제를 푸는 것이 우아하고 세련된 방법처럼 보일 수 있지만, 재귀 호출은 이를 사용하지 않는 경우에 비해 일반적으로 더 많은 비용이 들기 때문이다.

이어서 선행 재귀후행 재귀에 대해서도 설명해주고 있는데, 연결 리스트의 탐색 예제를 통해 설명해주는 부분이 나름 직관적으로 와닿았다.

그리고 재귀 호출과 메모리에 대한 내용이 있었는데, 특히 프로세스 주소 공간에 대한 설명은 꽤나 유용했다. 코드 영역, 데이터 영역, 스택 영역, 힙 영역 각각에 대해 간략하지만 핵심적인 설명이 있었으며 특히나 프로그램의 로딩부터 함수의 호출로 인한 메모리의 변화가 어떻게 일어나는지에 대해 설명하는 부분이 유용하다고 느껴졌다.

재귀를 사용할 때와 사용하지 않을 때 메모리의 상태 비교를 통해 책에서는 아래와 같이 이야기한다.

재귀 호출을 사용하면 메모리와 실행 시간 양 측면에서 비용이 증가합니다.

이에 이어 다음으로는 재귀 접근 방식이 가지는 두 가지 특징에 대해서 언급하는데 그 첫번째는 최적의 하위 구조로, 아래와 같이 설명하고 있다.

어떤 문제의 풀이법을 같은 문제의 더 작은 문제로 정의하는 게 최적의 풀이법이라면 이 문제는 최적의 하위 구조를 가졌다고 합니다. 최적의 하위 구조를 가진 문제는 다이내믹 프로그래밍 방법을 적용하기 좋은 문제입니다.

그리고 두번째 특징으로는 하위 문제의 반복 계산에 대해서 언급하는데, 책의 본문에서는 피보나치 수열 계산 문제에서의 하위 문제의 반복 계산을 예로 들고 있다. 그리고 이어서 하위 문제의 반복 계산이 발생하여 수행 시간이 증가하는 문제를 해결하기 위한 방법으로 메모 전략(메모이제이션)을 소개하는데, 이를 쉽게 말하면 어떤 하위 문제를 계산했을 때 그 결과를 일종의 캐시에 저장하여 같은 하위 문제를 다시 풀 때 이미 저장된 결과를 사용하는 방식을 의미한다. 또한 메모 전략에 대해서 아래와 같이 언급하고 있다.

메모 전략도 재귀 접근 방법에 속합니다.

메모 전략 = 재귀 호출 + 캐시 - 하위 문제의 반복 계산.

이어서 드디어 주인공인 다이내믹 프로그래밍에 대한 내용이 본격적으로 등장하는데, 가장 처음 알게된 것은 문제 해결의 방향이 재귀 호출, 또는 메모 전략은 하향식인 반면 다이내믹 프로그래밍은 상향식이라는 사실이었다.

앞에서 재귀 호출 또는 메모 전략을 통해 풀었던 예제들을 보여주면서 이를 다이내믹 프로그래밍으로 해결할 수 있음을 보여주는데, 이와 함께 직접 깃헙에 재귀 호출, 메모 전략, 다이내믹 프로그래밍의 실행 시간을 비교해볼 수 있는 예제 코드를 올려놨다는 점이 좋았다.

동일한 문제를 각각 하향식 접근 방법과 상향식 접근 방법로 풀어내는 예제 코드들로 하여금 그 둘이 어떤 차이점을 가지는지를 비교해볼 수 있었다.

그리고 결론적으로 다이내믹 프로그래밍은 재귀 호출 자체로부터 발생하는 부하를 피하기 위해 상향식으로 문제를 해결할 수 있다, 라는 내용을 전달하고 있었다.

더 나아가 그렇다고 다이내믹 프로그래밍이 은탄환은 아니라는 것에 대해서 설명해주는데, 하향식 접근 방법에서는 모든 하위 문제를 풀지 않고 전체 문제의 해답을 얻을 때 필요한 하위 문제만 풀었으나 상향식인 다이내믹 프로그래밍에서는 모든 하위 문제에 대해 계산을 수행하여 드물게 실제 필요한 것보다 훨씬 더 많은 하위 문제를 풀어야 하는 부작용이 발생하기도 한다는 점에 대해서 설명해주고 있다.

이에 이어 다이내믹 프로그래밍이 어떤 것이다, 라는 설명에서 그치지 않고 실제로 어떻게 적용할 수 있는지를 알려주는데, 다이내믹 프로그래밍을 사용해서 문제를 푸는 기본적인 순서는 아래와 같이 알려주고 있다.

  1. 재귀 호출을 사용한 풀이법 작성.
  2. 다이내믹 프로그래밍이나 메모 전략을 사용해 풀이법 개선.

그리고 어떤 문제가 다이내믹 프로그래밍 적용 가능 여부를 확인할 수 있는 체크리스트도 아래와 같이 알려주고 있다.

  1. 문제가 최적의 하위 구조를 가지고 있는지.
  2. 하위 문제를 반복 계산하는지.
  3. 최적화, 최대화 또는 최소화나 어떤 작업의 경우의 수를 구하는 유형의 문제인지.

더불어 다이내믹 프로그래밍을 적용하기 위한 단계식 접근법도 친절하게 알려주고 있다.

  1. 다이내믹 프로그래밍 적용 가능한 경우인지 확인.
  2. 점화식 또는 재귀 과정 정의.
    1. 문제를 하위 문제를 사용해 하향식으로 정의.
    2. 맨 아래에 해당하는 기본 경우에 대한 답을 정의.
    3. 종료 조건 추가.
  3. (선택적) 메모 전략 시도.
  4. 상향식으로 문제 풀이 도전.

위와 같이 실제로 적용할 수 있는 방법에 대해서도 설명해주고 있는 점이 상당히 유용하다고 느껴졌는데, 다이내믹 프로그래밍이 무엇인지 알았다고 해서 어디에 어떻게 사용해야 하는지 단번에 알 수 있는 건 아니라고 느꼈기 때문이다. 그리고 이러한 단계식 접근법을 여러 예제 문제들에 적용하는 과정을 보여주고 있다는 점에서 상당히 마음에 들었다.

이 책의 전체적인 소감은 이론적인 부분의 설명은 적당하게, 최대한 부담되지 않는 선에서 하면서 실제로 적용해볼 수 있는 여러 문제를 소개해주고 풀어내는 과정을 통해 재귀 호출과 메모 전략, 다이내믹 프로그래밍에 대해서 알려주는 실용적인 책, 이라는 것이었다. 본문 자체에도 꽤나 많은 예제들이 수록되어 있으며, 마지막 장인 5장은 아예 통째로 다양한 실전 문제들을 수록하여 위에서 안내해주는 단계식 접근법을 통해 풀어내는 과정을 보여주면서 연습문제를 통해 독자들 스스로도 한껏 두뇌를 사용할 수 있는 기회를 제공해주고 있다.

재귀 호출과 메모 전략, 다이내믹 프로그래밍에 대해서 관심이 있으나 아직 입문하지 못한 분들에게 추천하기 좋은 책이라는 생각이 든다.

코딩 테스트에서 꼭 빠지지 않고 출제되는 다이내믹 프로그래밍 문제.

빈도가 말해주듯이 중요하고 어려운 문제로 분류되어 확실한 개념을 알고 다양한 문제를 접해야 하는 파트이다.

그렇기 때문에 이 책은 코딩 테스트를 앞둔 사람들에게 추천한다. 제목처럼 다이내믹 프로그래밍을 완전 정복할 수 있게 개념을 다지기 좋은 책이기 때문이다. 

 

다이내믹 프로그래밍이 재귀 접근 방법에서 시작되어 문제 해결 순서에 따라 상향식, 하향식 방법으로 도달하는 과정을 설명하고 있다.

 

이 책의 구성을 살펴보면,

Par0t1에서 재귀 호출을 설명하며 다이내믹 프로그래밍의 기초를 설명한다.

점화식, 하노이탑, 피보나치수열 등 기본이 되는 예제들을 가지고 재귀 접근 방법을 설명하고 이 과정에서 발생하는 메모리 문제를 언급한다. 

언급한 문제에 대한 해결방안으로 메모 전략을 설명하므로써 흐름을 따라가며 이해가 쉬운 구조로 이루어져 있다.

 

Part2에서는 다이내믹 프로그래밍을 설명한다. 상향식, 하향식 접근 방법을 설명하고 하나의 예제를 다양한 방식으로 풀어내는 방법을 알려주고 있다.

용어 구분을 명확히 하고 비교를 통해 최적의 방법을 독자가 스스로 깨닫게 하고 있어 다이내믹 프로그래밍에 대한 헷갈리는 개념들을 이해하기 쉽게 설명하고 있다.

 

Part3에서는 앞서 설명한 개념을 다양한 실전 예제를 바탕으로 적용하는 연습을 한다. 독자가 배운 개념을 적용해보며 확실하게 이해할 수 있는 시간을 가질 수 있게 한다.

 

알고리즘을 처음 입문하고 여러 문제를 풀어본 뒤 다이내믹 프로그래밍에 흥미가 생기고 어려움에 부딪혀본 경험이 있다면

이 책을 통해 개념을 차근차근 이해하며 정립하는데 활용하면 가장 좋을 것 같다.

 

 

2.jpg

 

 

몇년전에 한 회사에 면접을 보러 간적이 있습니다.

면접질문에 "다이나믹 프로그래밍"에 대한 질문이 있었습니다.

하지만 저는 전혀... 그게 뭔지 몰랐습니다.

나름 책을 열심히 본다고 생각했는데, 아직 멀었구나 싶었습니다.

면접이 끝나고 돌아오면서 검색을 해봤는데, 내용이 좀 뜬금없었습니다.

"
"
수학과 컴퓨터 공학, 그리고 경제학에서 동적 계획법(動的計劃法, dynamic programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다.

(
위키백과)



이게뭐지.... 싶었습니다.

그리고,

근래 우연한 기회에 이 책을 입수하게 되었습니다. 책을 읽어보니 프로그래머 입장에서 "동적 계획법"을 어떻게 접근해야 하는 지 이해할 수 있었습니다.



일반적으로는 재귀함수를 사용해서 푸는 문제들이 다이내믹 프로그래밍의 대상이 되고요.

재귀함수는 사실 꼬리재귀에 대해 콜스텍을 소모하지 않게 언어에서 지원해주지 않으면, 쓰기 힘든 부분이 있는데요. 다이내믹 프로그래밍은 이를 다시 상향식으로 풀어서 더 빠르게 수행할 수 있는 방법을 제공해주는 이점이 있겠더군요.



저자는 단순히 다이내믹 프로그래밍을 설명하는데서 끝나지 않고,

알고리즘 예제를 몇 개 들면서, 독자가 충분히 그 과정을 이해할 수 있도록 배려하고 있습니다.



만약 알고리즘에 관심이 있는 독자라면 이 책을 천천히 읽으면서 도움을 받을 수 있을 것 같습니다.

 

1.jpg

 

 

 

두 달 전에 출간한 다이내믹 프로그래밍 완전정복, 언젠가 읽어보고 싶다고 생각했는데 기회가 찾아왔네요.

 

알고리즘을 전공 수업에서 원서로 추상적이고 원론적으로만 배워서 늘 부족한 느낌을 많이 받았었습니다. 그래서 다른 알고리즘 책들은 어떠한지 늘 궁금했습니다.

 

이 책은 전반적으로 다이내믹 프로그래밍이 메인 주제로 구성되어 있습니다. 책 크기도 작고 분량도 많지 않아 통학하며 가볍게 읽어볼 만 했습니다.

 

다이내믹 프로그래밍을 알고리즘 문제 풀이 전략으로 정의하고 재귀 호출, 메모 전략, 상향식 다이내믹 프로그래밍의 전략으로 알고리즘 문제에 접근합니다.

 

 

2_1.jpg

 

2_2.jpg

 

2_3.jpg

 

 

첫 챕터는 재귀 호출과 재귀 호출이 메모리에서 어떻게 올라가는지를 설명합니다.

유명한 하노이의 탑으로 시작해서 이진 트리 순회로 이어갑니다.

재귀 호출은 많은 함수의 호출이 이루어지는데, 이를 메모리 영역에서 어떻게 저장하는지를 간결하게 서술해 마음에 들었습니다.

 

 

3_1.jpg

 

3_2.jpg

 

 

두 번째 챕터는 메모 전략(memoization)을 소개합니다.

메모 전략을 왜 쓰는지, 메모 전략과 재귀 호출을 이용해 다이내믹 프로그래밍을 어떻게 하는지 서술합니다. 알고리즘 교재에서 많이 봤던 최소 거리와 최소 요금 문제를 예를 들어 설명합니다.

 

코드마다 주석이 상세하게 달려있어 복습도 빠르게 할 수 있어서 좋았습니다.

 

 

4_1.jpg

 

4_2.jpg

 

4_3.jpg

 

 

세 번째와 네 번째 챕터에서 다이내믹 프로그래밍을 본격적으로 소개하고

알고리즘 문제에 다이내믹 프로그래밍을 적용하기 전에, 확인해야 할 리스트들도 차근차근 설명합니다.

예제 문제 설명도 깔끔하고 용어 구분도 명확해서 빨리 이해할 수 있었습니다.

 

 

5_1.jpg

 

5_2.jpg

 

 

마지막 챕터는 실전 문제만 있는 장으로 여러 기본적인 알고리즘 문제들이 있습니다.

다이내믹 프로그래밍을 적용할 수 있는 이유와 여러 가지 접근 방법을 소개하고 시간 복잡도로 성능을 평가합니다.

 

백준, 경시대회류 같은 알고리즘 문제들은 없었지만 전공 수업에서 배웠던 예제들을 다시 복습하고 개념을 명확하게 잡을 수 있었습니다.

알고리즘을 처음 입문하거나 알고리즘 전공 수업 중 재귀, 메모 전략, 다이내믹 프로그래밍 부분이 곧잘 이해가 되지 않을 때 부교재로 활용하시면 좋을 것 같습니다.

 

 

 

E412FCDC-A0F8-45FD-9DDB-A5C2D025EB30.jpeg

 

 

 

 

<들어가며>

 

  학부 프로그래밍 수업 시간 초반에 나오는 것이 재귀함수이다. 보통은 팩토리얼을 구하는 방식으로 소개된다. 하지만, 나중에 프로그래밍을 깊게 배우게 되면, 재귀함수를 얼마나 조심히 써야 하는지를 배우게 된다. 

 

  하지만 개발자 생활을 15년 정도 해왔는데, 현업에서 재귀함수를 사용하는 경우는 많지는 않았다. 웹개발이 위주였는데백엔드 쪽에서 아주 가끔 쓰곤 했다. 하지만 실제로 팀원이 개발한 것을 보니, 이론을 제대로 공부 안했을 때 프로그램의성능이 얼마나 나빠질 수 있는지를 뼈져리게 느끼게 되었다. 그 뒤로 이러한 책을 종종 읽곤 한다. 

 

 

 

<추천 대상>

 

A. 취업이나 이직을 준비하며 코딩 면접을 준비하는 사람

 

B. 서버 개발이나 백엔드 개발을 많이하며, 프로그래밍 시 성능이나 메모리 사용을 많이 고려해서 개발해야 하는 사람

 

 

 

<요약>

 

Part 1. 재귀호출

 

재귀호출에 대해서 설명을 한다. 점화식, 팩토리얼, 하노이탑, 피보나치수열 등의 많이 쓰이는 예제로 설명을 한다. 추가로 재귀호출을 할 때 메모리가 어떻게 쓰이는 지에 대해서도 설명을 한다. 실제 현업에서 개발을 하게 되면 성능만 생각할게 아니라 메모리 사용량에 대해서도 크게 생각해야 한다. 

 

 

 

Part 2. 다이내믹 프로그래밍

 

다이내믹 프로그래밍의 개념에 대해서 설명한다. 피보나치 수열을 예로 들어 재귀, 다이내믹 프로그래밍, 메모 전략을 설명한다.

 

 

 

Part 3. 실전

 

Part 1, 2에서 배운 개념을 바탕으로 실전 예제를 위주로 설명을 한다. 여러 가지 예제를 들어가며 쉽게 설명한다. 앞의 1, 2파트에서 이론적으로 이해가 덜 갔던 부분들도 실제 예제를 보면서 이해될 수 있다. 

 

 

 

<마치며>

 

항상 그러하지만 학부 때 이론적으로 배운 것이 현업에서 얼마나 도움이 될까 고민하곤 한다. 하지만 실제 고성능을 요구하는 프로그래밍을 해야 하는 경우에는 이론적으로 공부했던 내용이 크게 도움이 되곤 한다. 이러한 면에서 성능을 고민해야 하는 사람들에게는 큰 도움이 될 것이라 생각한다.

 

 

dynamic_programming.png

 

‘다이내믹 프로그래밍’이라고 하면 프로그래밍하는 방법이나 이와 관련된어떤 것을 떠올리기 쉽다. 또는 ‘다이내믹’이라고 하는 언어가 있나? 하는 생각을 할 수 도 있다. 하지만 다이내믹 프로그래밍은 ‘동적 계획법’으로 알려진 문제 풀이 방식을 뜻한다. C, Java 와 같은 프로그래밍언어를 이용해서 코드를 작성하는 것은 주어진 문제를 푸는 과정에서 풀이 방법을 컴퓨터가 알아 들을 수 있도록 형식화하는 일이다. 이 책이 인도 사람(?)인 미나크시와 카말 라와트에 의해 영어로작성되었고, 그 책을 박상은 님이 우리말로 옮겼다. 다이내믹프로그래밍에 대한 내용을 전하고자 하는 같은 목적을 영어와 우리말이라는 서로 다른 형태로 나타낸 것과 같다. 책이어떤 언어로 쓰였느냐 보다 어떤 내용의 책이냐가 더 중요한 것처럼, 어떤 언어를 사용했느냐 보다 어떤방식으로 문제를 푸느냐에 집중할 필요가 있다.

 이책은 문제를 푸는 방법에 대한 이야기를 다루고 있다. 특히 보다 효율적으로 문제를 푸는 방법에 대한것이다. 단순히 정답을 얻는 것에 그치지 않고, 어떻게 하면더 빠르게, 더 적은 메모리로 문제를 풀 수 있을 지 고민하고 있다.예를 들어 역 사이 최소 요금 문제의 경우, 15개의 역에 대해 일반적인 재귀 방식으로문제를 풀면 535 msec이 걸리는 반면, 메모 전략을이용하면 1 msec 이 채 걸리지 않는다. 또한 250개의 역에 대해 메모 전략이 1492 msec 이 걸리지만, 다이내믹 프로그래밍을 적용하면 4 msec 만 소요됨을 나타내고있다. 그렇다고 언제나 다이내믹 프로그래밍이 최선의 결과를 가져오는 것은 아님을 이 책은 분명히 하고있다. 250개 중에서 10개를 추출하는 방법의 수를 나타내는조합(Combination)의 경우, 메모 전략의 경우 2msec이 걸린 반면, 다이내믹 프로그래밍은 9msec의 시간이 필요했다. 상향식 다이내믹 프로그래밍에서는 전체문제의 풀이에 도달하기 전 모든 하위 문제에 대해서 계산을 수행하게 되고, 따라서 드물게는 실제 필요한것보다 훨씬 더 많은 하위 문제를 풀어야 하는 경우가 생길 수 있는 것이다.

 이책은 크게 4개의 파트로 구성되어 있다. 첫번째 파트에서는재귀 호출에 대한 전반적인 이해를 돕고, 두번째 파트에서 다이내믹 프로그래밍에 대해 소개하며 적용 전략을다룬다. 세번째 파트는 실전 문제를 기반으로 재귀 호출로 푸는 방법과 다이내믹 프로그래밍을 이용한 방법에대해 이야기한다. 끝으로 네번째 파트는 원서에는 없지만 책의 내용을 보다 쉽게 이해할 수 있도록 하는시간, 공간 복잡도에 대한 기본 내용과 더불어 온라인 코딩 테스트 환경을 체험해 볼 수 있는 코딜리티사이트에 대한 간략한 소개로 마무리하고 있다.

 ‘좋은개발자가 되려면 프로그래밍 언어를 배우는 것보다 문제 해결의 기술을 습득하는 것이 중요합니다.’ 책의서문에 있는 말이다. 좋은 개발자를 꿈꾼다면 곁에 두고 자주 꺼내어 보길 추천한다.

 

2019년 10월에 출간된 <다이내믹 프로그래밍 완전 정복>에 대해 살펴보겠습니다. 출간한 지 얼마 되지 않은 신상입니다.

이 책의 저자는 미나크시(Meenakshi), 카말 라와트(Kamal Rawat)이며, 번역은 박상은 님께서 맡아주셨습니다.  개인적으로 이 책의 번역 품질은 만족스럽습니다. 

<다이내믹 프로그래밍 완전 정복>은 전에 리뷰했던 <파이썬 자료구조와 알고리즘>과 같이 작고 가벼워서 휴대하기 좋습니다. 물론 이 책의 내용을 휴대하며 스킴 방식으로 보는 것은 다소 이해하기 어렵겠지만, 반복해서 보기에는 좋을 것 같습니다.   

한빛미디어에서 기획하고 추진하는 한빛리더스 프로그램에 참여하며 작성한 글입니다. 

이 책에서 다루는 내용은?

<다이내믹 프로그래밍 완전 정복>의 처음 세 장은 재귀부터 시작하여 간단한 문제만을 다루고 있습니다. 기본 개념을 설명하고 독자가 쉽게 이해할 수 있도록 복잡한 부분을 과감히 배제하고 있습니다. 이후에는 조금씩 복잡한 문제를 다루고 마지막에는 실전 문제로 독자들이 다이내믹 프로그래밍을 이해했는지 평가할 수 있도록 구성되어 있습니다. 

이 책의 첫 번째 챕터는 재귀 호출에 관해 설명하고 있습니다. 재귀에 대한 기본 소개뿐만 아니라, 컴퓨터의 메모리 내부에서 재귀 호출이 어떻게 동작하는지 그림으로 충실하게 설명하고 있습니다. 컴퓨터에 익숙하지 않은 분들에게는 어려울 수 있는 내용이지만, 다이내믹 프로그래밍에 관심을 가질 만한 독자라면 반드시 이해하고 있어야 하는 내용이라고 생각합니다. 

두 번째 챕터는 재귀 호출에 대해 조금 더 나아갑니다. 피보나치 수열을 이용하여 재귀와 다이내믹 프로그래밍의 필요성을 언급한 후, 메모이제이션(이 책에서는 메모 전략이라고 함)을 설명하고 있습니다. 이 책에서 소개하는 메모이제이션에 대한 내용은 한 번 읽어봤으면 하는 챕터입니다.  

세 번째 챕터부터 다이내믹 프로그래밍의 세계로 들어갑니다. 재귀와 다이내믹 프로그래밍의 차이는 하향식 또는 상향식 접근 방법의 차이인데, 이 내용을 간단하면서도 명확하게 소개하고 있습니다. 일반적으로 상향식 접근 방법으로 문제를 풀이하는 것이 좋은데, 특정 상황에서는 하향식 접근 방법이 유리한 경우도 있습니다. 이런 상황을 설명하고, 실수할 수 있는 부분에 대해 주의사항을 안내합니다.

네 번째 챕터는 다이내믹 프로그래밍의 훈련을 돕기 위해 재미있는 문제들을 제시하고, 문제 풀이를 유도합니다. 이 문제들의 난도는 앞에서 살펴본 것보다는 높은 수준이지만, 지금까지 꼼꼼히 따라왔다면 충분히 풀 수 있는 문제들로 구성되어 있습니다. 직접 풀이해보면 다이내믹 프로그래밍에 한 걸은 다가갈 수 있을 것으로 생각합니다. 

마지막 챕터는 다이내믹 프로그래밍에 익숙해지도록 조금 더 어려운 문제들로 구성되어 있습니다. 실제 입사 문제의 난도로 구성된 문제들도 포함되어 실전 테스트라 생각하고 접근하면 좋을 것 같습니다. 만약 풀이하지 못하더라도 꾸준히 연습하고 다양한 방법으로 풀이해보면 큰 도움이 될 것으로 확신합니다. 

마치면서

<다이내믹 프로그래밍 완전 정복>은 네 개의 파트와 다섯 개의 챕터, 그리고 두 개의 부록으로 구성(약 220페이지 분량)되어 있습니다. 생각보다 매우 얇은 책이지만, 이 책의 품질은 나쁘지 않습니다. 간단명료하게 잘 설명된 개념 소개로 독자의 이해를 돕고 있으며, 문제를 해결하는 방법을 매력적으로 정리하고 있습니다. 

이 책은 프로그래밍에 재미를 붙이고, 다이내믹 프로그래밍에 대해 더 많은 경험을 하고 싶은 분에게 추천하고 싶습니다. 이 책은 재미있는 연습문제를 포함하고 있습니다. 이 문제의 풀이 방법을 생각하면 시간이 흐르는 줄 모르고 문제 풀이를 하는 모습을 발견할 수 있을 것입니다.

마지막으로 이 책은 C 언어를 기준으로 설명하고 있습니다. C 언어를 모르는 독자라면 이 책의 내용을 이해하기 어려울 수 있습니다. 이 책의 역자인 박상은 님은 우수한 번역 품질에 C 언어로 작성된 코드를 파이썬으로 재구현하여 코드를 제공합니다. 비록 파이썬으로 코드를 설명하지는 않지만, 파이썬을 이해하고 있는 독자라면 도움을 받을 수 있을 것입니다. C 언어가 생소한 독자들을 위해 파이썬으로 설명한 책도 출간했으면 하는 개인적인 바람이 있습니다. 

다운로드.png

 

사실 알고리즘에 대해서 굉장히 지식이 약했던 나로써 알고리즘 공부를 시작함과 동시에 요즘 추세인 동적프로그래밍이 이 최신 트랜드라는 것을 알고 인터넷으로 공부를 시작 하였는데, 생각보다 인터넷에 나오는 내용 수준 자체가 이미 높은 상태라 받아들이기 힘들었는데 이 책을 보면서 동적프로그래밍이 무엇인지, 다이내막 프로그래밍이 무엇인지 아주 기초부터 원리 동작 방식, 해결방법들을 자세하게 풀어놓은 책이라 동적프로그래밍이 무엇인지 한발짝 나간것 같은 느낌이든다. 사실 이책이 처음부터 쉽게 써져있다고 말 할 수는 없다. 기초적인 프로그래밍 개념이 있어야 하며(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 0
def 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 0
R, 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 0
def 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 cnt
return count(num)def countWaysDP(self, num):
if num == 0:
return 0
dp = [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 0
dp = [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 0
def 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 subProfit
return 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 0
dp = [[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 0
R = 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가 가장 유명한 편이다. 우리나라에서도 점점 많은 회사들이 도입하고 있기 때문에 시간 날 때마다 풀어보면서 익숙해지는 게 좋다.

소소한 장점

원서는 c source인데 역자가 python으로 옮겨놓았다 https://github.com/crapas/dp

중간중간 박스를 통해 실제 인터뷰에서 유용할 팁을 알려주는 경우가 있다. 원서 제목 자체가 Dynamic Programming for Coding Interviews이니 적절한 설명이라고 생각한다.

소소한 단점

(리디북스 한정) 역시나 매번 그렇듯 옮긴이의 말에 있는 링크는 정상 동작하지 않는다. 사소한 버그이지만 리디북스의 프로그래밍 책을 읽는다는 특성상 컴퓨터에서 읽는 경우가 많은데 링크가 동작하지 않으면 불편하다.

Site

 

[기초]

 

다이내믹 프로그래밍은 흔히 [동적 계획법]이라고 변역하는 알고리즘 접근 방법론이다. 개발 방법론은 아니다. 문제 풀이 방식에 가깝다. 다이내믹 프로그래밍은 하위 문제를 한 번만 계산하는 상향식 문제 풀이 접근법이다. 따라서 직관적인 재귀 호출보다는 이해하기가 상대적으로 어려운 경우가 많다.

 

[대상 독자]

 

코딩 면접을 앞두고 있는 개발자나 알고리즘 대회 참가를 앞두고 있는 학생을 위한 책이다.

 

[구성]

 

책은 세로 길이가 손바닥을 편친 것만할 정도로 자그마하며, 총 페이지가 220페이지 정도로 아주 얇다. 내용은 재귀 호출의 이해부터 시작하여, 다이내믹 프로그래밍의 이해, 적용 전략, 실전 문제 순으로 구성되어 있다. 다이내믹 프로그램에 빠르게 익숙해지기를 원하는 사람들을 위한 구성이다. 앞에서는 보다 단순한 개념 위주로 설명을 시작하지만, 뒤로 갈수록 페이지를 넘기는 것이 점점 더 어려워진다. 난이도가 올라갈수록 멈추고 생각해야하는 지점이 늘어나기 때문이다.

 

[장점]

 

무엇보다 좋았던 점은 번역의 정확도와 자연스럽게 읽히는 한글 문장의 완성도이다. 그리고 시간 복잡도와 공간 복잡도라는 개념을 이해하지 못하는 초보자들을 위해서, 원서에 없는 기본적인 내용을 먼저 읽어볼 수 있도록 부록에 추가한 점이 좋았다. 또한 책 구성도 하나의 주제에 잘 집중해서 체계적으로 설명을 진행해나간다는 점이 눈에 띈다.

 

[단점]

 

C언어로 씌여진 책이다. 출판사의 깃허브(http://github.com/crapas/dp)에서 파이썬으로 된 코드도 제공하기는 하나, 본문의 설명은 오직 C언어 기준으로만 적혀 있기에, C언어의 기본 문법과 포인터, 메모리, 성능에 대한 기본적인 이해가 있지 않다면 제대로 이해하기가 어려울 것 같다.

 

[후기]

 

업계에 발을 오래 담그고 있음에도 전통적인 프로그래밍, 그 중에서도 면접 대비용 알고리즘 책은 오랜만에 보는 느낌이다. 그래도 다이내믹 프로그래밍에 대한 기본적인 개념들을 이해하고 정리하기에는 좋았다. 맨 뒤 챕터의 문제까지는 다 못풀었지만 말이다. 내 분야가 코드 자체의 성능보다는 외부 요인이 더 많은 분야라서, 더 효율적으로 코드를 작성하기 위해서 꼭 필요한 지식을 너무 잊어버린게 아닌가 약간의 반성도 가져다 준 책이다.

다이나믹 프로그래밍은 컴퓨팅 분야에서 어려운 주제중 하나이다. 

최적화 문제를 풀기위해 , 재귀적 호출, 메모 전략, 다이나믹 프로그래밍 기법을 소개한다. 

하향식 접근법과 상향식 접근의 차이점, 다이나믹 프로그래밍의 적용 사례를  천천히 음미하며 ,  프로그래밍 기술을  업그레이드할 수 있는  기회를 가지게 될 것이다. 

거스름돈 최적화,  0-1 배낭 문제, 최장 공통 부분 수열 문제를  풀어보며,  다이나믹 프로그래밍 기법의 진수를 맛보게 될 것이다. 

 

부담없이 동적 프로그래밍 기법을 현업에서도 적용할 수 있는 기회를 가지기 바란다.  

 

KakaoTalk_20191117_225611465.jpg

 

KakaoTalk_20191117_225554519.jpg

 

 

 

설명이 굉장히 상세합니다. 초보자들은 디피 점화식이 왜 이렇게 짜여지는지 이해못하는 경우가 많은데 그 부분을 상세히 설명해줍니다. 강추하는 책!!

코딩 면접 광탈에서 멘탈갑으로 거듭나기

출퇴근 시간에 이 책을 읽고 뒤를 보았을 때,

'바로 이거네' 하고 싶을 정도로 공감이 갔습니다.

이 책은 제게 그런 책이었습니다.

 

계속 보게 만드는 재미와 매력이 있는 책

이 책은 계속 보게 하는 매력이 있었습니다.

책의 제목인 동적 프로그래밍이 난이도가 있는데도

이 책은 이야기를 잘 풀어냈습니다.

 

초반에 조금 보다가 '난 안되나 보다' 하고

구석에 모셔놓음을 허락지 않으려는 노력이라고 해야 할까요?

이 책은 이야기를 독자들에게 흥미를 갖게 하면서,

나도 할 수 있다는 자신감을 가지게 하는 책입니다.

 

하나의 문제를 가지고 이 책이 이야기하는 흐름을 이해하다 보면

'코딩 테스트에서 이렇게 하면 되겠구나' 하는 감이 옵니다.

중요한 것은 그 감이라는 게 확실하게 온다는 것입니다. :-0

 

그래서 이 책은

코딩 테스트가 부담스러웠던 저와 같은 분들에게는

좋은 선택이 될 수 있습니다. 학부생들에게도 이 책은

큰 힘이 되어 줄 수 있으리라 생각됩니다.

 

이 책은 유능한 선생님 같다고 할 수 있겠네요.

요즘 알고리즘 책이 많아졌다. 웹 프로그래밍을 하면서 알고리즘에 대해서 많은 고민을 거의 하지 않았다. 나의 경우는 실제로 실무에서는 그런 알고리즘을 생각할 일이 거의 없었다.

이번에 프로젝트를 하면서 데이터베이스에서 중복을 최소화하기 위함 등등의 목적으로 재귀쿼리를 많이 사용하는 것을 봤다. 그 만큼 소스는 복잡해졌지만 table에 수는 많이 없게 되었다.

MSA를 한다고 하면 대부분 table보다는 소스(app)에서 재귀함수를 활용할 수 있지 않을까 생각해 보게 되었다.

이 책에 처음에 재귀함수가 나와서 좋았다. 책 표지에도 '넌 이미 재귀를 능가했다'라고 적혀있다.

 

많은 알고리즘 책이 있지만, 한번도 봤다면 얇은 알고리즘 한권쯤 보는 것도 좋을 것이다.

20191116_193402.jpg

 

 

이 책을 처음 보고 느낀 점은 "얇다"였습니다. 200장 정도의 분량과 작은 크기에 다이나믹 프로그래밍에 대한 내용을 제대로 담았을까 라는 생각이 들었습니다.

 

하지만 걱정과는 다르게, 개념이 간단 명료하게 잘 설명되어 있고 문제를 해결해 나가는 순서를 잘 정리해 놓았다고 생각이 들었습니다.

 

개인적으로 다이나믹 프로그래밍은 주요 유형의 문제들을 반복해서 풀면서 감을 잃지 않는 것이 중요하다고 생각하는데, 이 책으로 문제를 반복해서 풀기 전에 빠르게 한번 정리하고 들어가면 좋을 것 같다고 생각했습니다.

 

빠르게 다이나믹 프로그래밍을 살펴보고 싶으신 분 또는 문제를 다이나믹 프로그래밍으로 풀어나가는 사고 과정을 익히고 싶은 분들에게 추천합니다.

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

책 표지

1

이 책을 읽어야 할 이유

순전히 책 표지에 끌렸다. 물론 책이 매우 얇은 점도 한 몫했다. 책 표지에서 알 수 있듯이 이 책은 재귀와 관련된 내용을 주로 다룬다.

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(DP)


프로그래머 혹은 컴퓨터 공학도라면 누구나 이 무서운 단어들을 들어봤을 것이다. 대부분의 프로그래머는 이런 용어가 세상에 존재하는구나 하는 정도로 넘어가고 잊어버린다. 이 단어들은 프로그래머에게 왜 무서운 단어가 되었을까? 먼저, 본 도서의 장점을 전달하기 위해 필자가 겪었던 다이내믹 프로그래밍 경험을 말씀드리고자 한다.

  • 이름부터가 직관적이지 않다.
    본 도서 서문 “옮긴이의 말”에서 역자는 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 두종류의 언어로 제공된다. 두 언어를 모두 활용한다면 보다 이해도를 높일 수 있다.

  • 기타
    끝으로 본 도서를 학습하며 도움이 될만한 유용한 참고자료를 아래 링크로 남긴다.

누가 읽어야 하는가?


  • 프로그래머 누구나(특히 면접시험을 앞둔 프로그래머)

  • 재귀호출과 다이내믹 프로그래밍에 정면 도전하고 싶은 분

  • AI분야의 프로그래머(특히 강화학습, NLP에 많은 도움이 됨)

책의 구성 및 요약


이 책은 크게 세부분으로 구성되며, 각 파트에서 다루는 내용을 아래와 같이 요약해 보았다.

  • 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 로 문제를 풀어야하는지 상향식 하양식 방식은 어떤 경우에 다르게 풀어야 하는지에 대하여 잘 나와있습니다.막연하게 재귀로 풀면 좋다가 아니라, 재귀로 풀면 프로세스나 메모리 구조로 이런 점이 더 좋다는 점을 알 수 있어서 더 이해하기 쉬웠던것 같습니다. 
 

이 책은 면접자를 위한 실용서 로 만들어진 책이다.

면접 주제 중 가장 어려운 부류인 다이내믹 프로그래밍을 다루고 있으며, 언어는 C언어를 사용하여 코드를 붙여놓았다.

1단계: 개념 설명

2단계: 문제 적용

3단계: 유의점 및 요점 정리

 

4단계: 연습문제 풀기

로 보통 구성되어 있습니다.

문제 풀이에 있어서도 그래프 및 타일등의 시각적 자료를 이용하여 최대한 면접자들의 이해를 도왔고,

배운 개념에 대해 다시한번 적용해 볼수 있는 문제를 준비해 놓아 복습이 필요없는 교재라고 볼 수 있습니다.

이 책의 추천 대상 : 알고리즘 면접이 두려운 학생및 취준생 분들, 알고리즘 중에 특히

다이내믹 프로그래밍에 어려움을 겪는 분들, '상향식 문제 풀이법'이 무엇인지 모르는 입문

자분들께 이 책을 추천 드리고 싶습니다.

 

 


<나는 리뷰어다> 10월 이벤트 당첨으로 작성한 리뷰 입니다.


[한줄평]

재귀적 사고에서 다이내믹 사고로 전환하기에 최적의 도서입니다.


[목차구성]

[PART 1 재귀 호출의 모든 것]

CHAPTER 01 재귀 호출의 이해

CHAPTER 02 재귀 호출의 특징과 메모 전략


[PART 2 드디어 다이내믹 프로그래밍]

CHAPTER 03 다이내믹 프로그래밍의 이해

CHAPTER 04 다이내믹 프로그래밍 적용 전략


[PART 3 지금부터 게임을 시작하지]

CHAPTER 05 실전 문제

[PART 4 부록은 덤이다]

APPENDIX A 알고리즘의 효율성(시간과 공간 복잡도)

APPENDIX B 코딜리티 활용하기


[대상 독자]

코딩 면접을 준비하는 개발자

코딩 알고리즘 경진대회를 준비하는 학생


[이 책의 주요 특징]

- 재귀 호출의 A to Z

- 재귀 호출과 메모리 구조의 관계

- 최적의 하위 구조 + 하위 문제의 반복 계산

- 메모 전략을 활용한 재귀 호출 성능 개선

- 하향식 접근 vs 상향식 접근

- 다이내믹 프로그래밍 기초부터 문제 풀이 전략까지

- 부분집합의 합, 최장 공통 부분 수열, 0-1 배낭, 회문 등 실전 문제 풀이


[서평]

 

개발자로 취업을 하려면 코딩면접을 봐야 한다. 운이 좋게 자주 나오는 알고리즘 문제를 외워서 나오면 다행이지만 새로운 유형이 나오면 멘붕이 올것이다. 이책은 알고리즘 공부 어려움 점을 쉽게 해결 할수 있는 다이내믹 프로그래밍을 배울수 있다. 재귀호출,메모전략, 상향식 다이내믹 프로그래밍의 개념을 자세히 설명하고 단골로 출제되는 알고리즘 문제부터 인터뷰 문제까지 다양한 예제에 적용을 하고 있다. 외워서 알고리즘을 푸는 것이 아니라 알고리즘적 생각 다이내믹 프로그래밍을 이해하고, 문제 풀이에 적용할수 있는 능력을 배울수 있을 것입니다.


 

알고리즘에서 가장 많이 사용되는 기법 중 하나가 재귀함수 이며 그것을 뒤 잇는 알고리즘 기법이 다이내믹입니다.

그만큼 다이내믹의 기초 알고리즘으로 중요하다고 여겨 지는데요.

10월 리뷰어 책 중에 다이내믹 프로그래밍 완전 정복이라는 책이 있어서 신청 후에 빨리 읽어 보고 싶어서 기다리고 있었기에 도착하자 마자 얼른 뜯어서 확인을 해 보았네요.

역시 다이내믹은 재귀함수의 개념을 잡기 전에 설명하기에는 좀 어려운 부분이라서 그런지 먼저 재귀함수에 대해서 개념을 설명해 주고 있었습니다.

일반적인 알고리즘 책을 보면 다이내믹은 한 chapter 정도의 분량으로 다이내믹은 이런거야 정도로 설명을 해 주고 있는데...

이 책은 다이내믹은 이런것이야를 설명하기 위해서 기본적으로 알아야 할 재귀함수 부터 자세히 설명이 되어 있네요.

 

 

면접 하루 전이면서 다이내믹 프로그래밍의 달인이라면 4장 5장을 읽고

면접 하루 전이면서 프로그래밍에 익숙하다면 2장 3장을 읽어 보라고 하네요.^^

저는 면접 준비가 아니라서 시간이 넉넉한 편이니 첫장 부터 읽기로 했습니다.

PART 1 에서는 재귀호출의 모든것 에 대해 기술합니다.

재귀호출 시 사용하는 스택 메모리 부터 최적의 하위구조 특성을 가진 문제를 풀기 위한 전략

메모이제이션 기법을 활용한 하향식 다이내믹 기법 등에 대해 설명을 하고 있습니다.

PART 2 에서는 다이내믹 프로그래밍이 무엇인지를 다루고 여기에 따른 상향식 접근과 하향식 접근 방법을 다루고 있습니다.

또한 다이내믹 프로그래밍을 적용하기 위한 전략적인 부분으로 행렬에서 최소이동 비용구하기 문제를 풀어 나가는 과정을 예를 들어 설명합니다.

먼저 재귀호출을 이용한 풀이 방법을 보여 주고 있으며 이러한 문제는 전체의 모든 경우를 찾아 가게 됨에 따라 시간적인 활용이 무척이나 더디지만...

실제적으로 프로그래밍을 설계하는 과정에서 바라 보았을때는 단위별로 설계하기에는 재귀적으로 생각해 보는 것이 설계하는 것이 간단해 집니다.

이것을 좀더 개선 하여 메모이제이션 기법을 활용한다면 하향식 다이내믹 기법이 되는 것입니다..

이렇게  메모 기능을 활용하여 구현 해 본 후에 이것을 상향식으로 생각해 본다면 어떤 식으로 설계를 해 볼 것인지 생각해 보고..

이것을 상향식으로 설계를 해 보게 됩니다.

이때 고려해야 할 점은 재귀호출을 제거하고 기본경우에서 거꾸로 출발하는 진행방향을 재설계 하게 됩니다.

 

다이내믹으로 설계하기 위한 전략

 

이 문제 뿐 아니라 다양한 문제를 통해서 다이내믹을 설계하는 연습을 하게 됩니다.

 

 

마지막으로 연습문제와 함께 해당 장에서 공부를 해야하는 정리까지도 해 주면서 다시 한번 제대로 이해 했는지 확인을 하게 됩니다.

 

PART3 에서는 지금부터 게임을 시작하지 편입니다.

다양한 실전 문제를 통해서 알고리즘 대회를 준비하는 학생들이라면 한번쯤은 풀어 보아야 할 문제들이 주어지고 풀이와 설명을 통해 실력을 향상시켜 나갑니다.

이때에는 시간이 충분히 된다면 책으로 먼저 풀어 보는 것이 아닌 문제를 읽고 먼저 풀어 보고 그 다음 자신의 코드와 책의 설명이 어떻게 다른지에 대해 비교하게 된다면 더 많은 것을 얻을 수 있을것이라 생각합니다.

PART4 에서는 부록은 덤으로 주는데요.

알고리즘의 시간복잡도, 빅오표기법,공간복잡도 등을 살펴 보게 됩니다.

알고리즘 공부하는 사람이라면 시간복잡도나 빅오표기법 등은 기본적으로 알고 설계를 해 나갈 수 있어야 하는데요.

이런 부분들에 대해서 집고 넘어 갈 수 있는 부록까지도 내용이 착해서 너무 좋은 책이 아니었나 싶네요.

 

이 책은 알고리즘 공부를 하는데 다이내믹에 대한 개념이 잘 안 잡혀 있다면 한번쯤은 정독을 해 보시길 권해 드립니다.

알고리즘 공부에서 재구호출과 다이내믹은 정말 알고리즘의 기본이 아닐까 생각 되는데요.

이러한 부분들이 대부분 코딩면접에서 자주 나오는 유형 중에 하나이기 때문에...

알고리즘 대회나 코딩 면접을 준비하는 분들이라면 한번쯤 보시면 좋지 않을까 생각이 되네요.

또한 이 책의 장점 중 하나가 원본은 C언어 기반이지만...

역자가 파이썬으로 코드를 작성해서 깃허브에 제공해 주고 있다는점.

꼭 C언어를 아는 사람이 아니라 파이썬 만으로도 이 책의 코드를 실행해 볼 수 있다는 점이 매력적이지 않나 싶습니다.

이 책의 내용을 미리 보기 하시려면 

http://www.hanbit.co.kr/store/books/look.php?p_code=B9440449667

 

 

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

다이내믹 프로그래밍(동적 계획법)은 알고리즘을 공부하다 마주치는 첫 번째 큰 장벽이다. 이 책은 알고리즘 공부의 걸림돌을 디딤돌로 만들기 위해 다이내믹 프로그래밍이라는 한 가지 주제만을 철저히 파고든다.

www.hanbit.co.kr

 

에서 좀더 자세한 내용을 확인 하실 수가 있습니다.

 

결제하기
• 문화비 소득공제 가능
• 배송료 : 2,000원배송료란?

배송료 안내

  • 20,000원 이상 구매시 도서 배송 무료
  • 브론즈, 실버, 골드회원이 주문하신 경우 무료배송

무료배송 상품을 포함하여 주문하신 경우에는 구매금액에 관계없이 무료로 배송해 드립니다.

닫기

리뷰쓰기

닫기
* 도서명 :
다이내믹 프로그래밍 완전 정복
* 제목 :
* 별점평가
* 내용 :

* 리뷰 작성시 유의사항

글이나 이미지/사진 저작권 등 다른 사람의 권리를 침해하거나 명예를 훼손하는 게시물은 이용약관 및 관련법률에 의해 제재를 받을 수 있습니다.

1. 특히 뉴스/언론사 기사를 전문 또는 부분적으로 '허락없이' 갖고 와서는 안됩니다 (출처를 밝히는 경우에도 안됨).
2. 저작권자의 허락을 받지 않은 콘텐츠의 무단 사용은 저작권자의 권리를 침해하는 행위로, 이에 대한 법적 책임을 지게 될 수 있습니다.

오탈자 등록

닫기
* 도서명 :
다이내믹 프로그래밍 완전 정복
* 구분 :
* 상품 버전
종이책 PDF ePub
* 페이지 :
* 위치정보 :
* 내용 :

도서 인증

닫기
도서명*
다이내믹 프로그래밍 완전 정복
구입처*
구입일*
부가기호*
부가기호 안내

* 온라인 또는 오프라인 서점에서 구입한 도서를 인증하면 마일리지 500점을 드립니다.

* 도서인증은 일 3권, 월 10권, 년 50권으로 제한되며 절판도서, eBook 등 일부 도서는 인증이 제한됩니다.

* 구입하지 않고, 허위로 도서 인증을 한 것으로 판단되면 웹사이트 이용이 제한될 수 있습니다.

닫기

해당 상품을 장바구니에 담았습니다.이미 장바구니에 추가된 상품입니다.
장바구니로 이동하시겠습니까?

자료실

최근 본 책0