한빛출판네트워크

IT/모바일

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

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

한빛미디어

번역서

판매중

좋아요: 4
  • 저자 : 미나크시 , 카말 라와트
  • 역자 : 박상은
  • 출간일 : 2019-10-04
  • 페이지 : 220쪽
  • ISBN : 9791162242063
  • 물류코드 :10206

합계 : 16,200

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

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

     

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

     

     

    주요 내용

    • 재귀 호출의 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 코드로 작성되었으나 역자가 밤을 새워 파이썬 버전 코드도 작성해 깃허브로 제공한다. 

     

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

    •  



      [기초]


       


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


       



      [대상 독자]


       


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


       


      [구성]


       


      책은 세로 길이가 손바닥을 편친 것만할 정도로 자그마하며, 총 페이지가 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




       


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


       

  • 내용이 없습니다.
  • 내용이 없습니다.
닫기

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