확장메뉴
주요메뉴


소득공제
미리보기 공유하기

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

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

리뷰 총점9.3 리뷰 15건 | 판매지수 522
베스트
IT 모바일 top100 1주
정가
18,000
판매가
16,200 (10% 할인)
YES포인트
당신의 독서를 위한 친구 - 심플 폴더블 LED 독서등/크리스탈 문진/가죽 슬리브 유리 텀블러/모나미 볼펜
8월 얼리리더 주목신간 : 귀여운 방해꾼 배지 증정
월간 개발자 2022년 8월호
박해선 저자의 머신러닝/딥러닝 패스
[단독]『혼자 공부하는 파이썬』 개정판 출간
내일은 개발자! 코딩테스트 대비 도서전
[단독] 에듀윌 IT 자격증 기획전 - 가장 빠른 합격출구 EXIT
2022 하반기 공채 이벤트
YES24 트윈링 분철 : 인서트라벨/스티커 택1 증정
8월 전사
쇼핑혜택
1 2 3 4 5

품목정보

품목정보
출간일 2019년 10월 04일
쪽수, 무게, 크기 220쪽 | 153*223*20mm
ISBN13 9791162242063
ISBN10 116224206X

이 상품의 태그

책소개 책소개 보이기/감추기

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


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

목차 목차 보이기/감추기

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

저자 소개 (3명)

출판사 리뷰 출판사 리뷰 보이기/감추기

알고리즘 공부의 걸림돌 극복하기
다이내믹 프로그래밍을 이보다 더 자세히 설명한 책은 없다


재귀, 정렬, 검색까지 순조롭게 알고리즘을 공부하다 마주치는 첫 번째 장벽이 바로 다이내믹 프로그래밍(동적 계획법)이다. 재귀에서 다이내믹 프로그래밍으로 사고를 바로 전환하기가 어렵다 보니 많은 사람이 여기서 좌절하게 된다. 하지만 이 걸림돌을 제대로 마스터하기만 한다면 올림피아드 문제도 코딩 인터뷰도 누구보다 빠르게 남들과는 다르게 돌파할 수 있다.
이 책은 알고리즘 공부의 걸림돌을 디딤돌로 만들기 위해, 코딩 면접 광탈에서 멘탈갑으로 거듭나기 위해 다이내믹 프로그래밍이라는 한 주제만을 처음부터 끝까지 철저히 파고든다. 재귀 호출, 메모 전략, 다이내믹 프로그래밍 세 가지 개념을 자세히 설명하고, 문제 풀이에 이들을 적용해 성능을 개선해나가는 전략을 익힐 수 있다.

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

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

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

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

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

주요 내용

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

회원리뷰 (15건) 리뷰 총점9.3

혜택 및 유의사항?
다이내믹 프로그래밍 완전정복 내용 평점5점   편집/디자인 평점5점 스타블로거 : 블루스타 아***인 | 2020.05.30 | 추천0 | 댓글0 리뷰제목
개요본 리뷰는 한빛미디어 출판사 "다이내믹 프로그래밍 완전정복(미나크시, 카말 라와트 저)"을 읽고 얻은 지식을 정리한 글입니다.목차무서운 재귀, 더 무서운 Dynamic Programming(DP)다이내믹 프로그래밍을 위한 본 도서의 장점누가 읽어야 하는가?책의 구성 및 요약요약하며…무서운 재귀, 더 무서운 Dynamic Programming(DP)프로그래머 혹은 컴;
리뷰제목

개요

본 리뷰는 한빛미디어 출판사 "다이내믹 프로그래밍 완전정복(미나크시, 카말 라와트 저)"을 읽고 얻은 지식을 정리한 글입니다.

무서운 재귀, 더 무서운 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를 뽀개 완전히 두려움을 없애고 싶은 분께 꼭 일독을 권한다.

댓글 0 이 리뷰가 도움이 되었나요? 공감 0
포토리뷰 다이내믹 프로그래밍 완전 정복 : 빠르고 우아한 상향식 문제 풀이법 내용 평점5점   편집/디자인 평점5점 스타블로거 : 수퍼스타 좋**상 | 2019.12.15 | 추천4 | 댓글0 리뷰제목
요즘 가장 각광받고 있는 업종 중 하나가 바로 프로그래밍 분야일 것이다.프로그램을 통해 새로운 것을 만들어 내는 기쁨은 예술가의 그것과 다르지 않을 것이다.문제는 책을 통해 컴퓨터 언어만을 공부하면 누구나 프로그래머가 되는 것은 아니라는 것이다.초보자는 책을 통해 배운 내용만으로도 충분할 수 있으나 어느 단계를 넘어가기 시작하면 어려움에 봉착한다.컴퓨터 전공자들이;
리뷰제목

요즘 가장 각광받고 있는 업종 중 하나가 바로 프로그래밍 분야일 것이다.

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


흔히 동적 계획법이라고도 하는 것으로 프로그래머로써 레벨업을 위해 반드시 넘어야 하는 것이다.
프로그램을 전문적으로 하는 큰 회사에 입사하기 위해서는 코딩 테스트를 위해 꼭 알아야 하는 것이기도 하다.
프로그램에는 정답이 없다.
시스템 특성에 따라, 언어에 따라, 심지어 환경에 따라 답이 달라질 수 있다.

우리가 다이내믹 프로그래밍을 알아야 하는 이유는 알고리즘을 통해 코딩의 질을 높이고 단순화할 수 있기 때문이다.
책의 시작은 '재귀 호출'로 시작하고 있다.
재귀야 말로 알고리즘의 효용성을 극대화하고, 프로그래머의 실력을 검증할 수 있는 좋은 코딩 테스트 중 하나이다.
특정 프로그래밍 언어에 대한 숙련도가 아니라 해당 문제의 논리적 이해도와 창의적 해결방법을 확인할 수 있다.
그 다음으로 '다이내믹 프로그래밍'을 보여주고 있다.
상향식 프로그래밍이 무엇인지, 언제, 어떻게 사용하는지, 그리고 언제 사용하면 안되는지 등 다이내믹 프로그래밍의 모든 것을 보여주고 있다.

마지막의 실전 문제는.... 솔직히, 아직 모두 풀어보지 못했다.
앞서 말한 바와 같이 다이내믹 프로그래밍은 언어의 숙련도와 상관없이 알고리즘에 대한 깊은 이해가 있어야 한다.
알고리즘은 당연히 수학적 지식을 바탕으로 한다.
주변의 개발자들 중 더 나은 알고리즘을 만들기 위해 고등학생때 보았던 수학 책을 다시 펼치는 분들도 있다.

대부분 알고리즘의 책들이 자바나 C로 설명하고 있는데 이 책은 파이썬 소스를 제공하고 있다는 것이 마음에 들었다.
원본은 C 소스만 제공하고 있으나, 출판사에서 번역을 하면서 파이썬 코드를 별도로 제공하고 있다.
솔직히 이것이 내가 이 책을 보게 된 이유 중 하나이기도 하다.


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

댓글 0 4명이 이 리뷰를 추천합니다. 공감 4
[도서리뷰] 다이내믹 프로그래밍 완전정복 내용 평점3점   편집/디자인 평점3점 YES마니아 : 로얄 b*****e | 2019.12.15 | 추천0 | 댓글0 리뷰제목
안녕하세요, 괴짜 개발자 namedboy 입니다. ??여러분은 알고리즘을 공부할 때 어떻게 하시나요?지난번 제가 포스팅 했던 게임으로 익히는 코딩 알고리즘 책에 나오는 코딩게임 같은 웹사이트도 좋고 예전부터 알고리즘 연습 사이트로 유명한 leetcode, codility도 좋다고 생각합니다.예전에는 무조건 책을 보고 알고리즘을 연습해야 했는데 요즘은 다양한 방식으로 알고리즘을 풀어볼 수;
리뷰제목

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


여러분은 알고리즘을 공부할 때 어떻게 하시나요?

지난번 제가 포스팅 했던 게임으로 익히는 코딩 알고리즘 책에 나오는 코딩게임 같은 웹사이트도 좋고 예전부터 알고리즘 연습 사이트로 유명한 leetcode, codility도 좋다고 생각합니다.

예전에는 무조건 책을 보고 알고리즘을 연습해야 했는데 요즘은 다양한 방식으로 알고리즘을 풀어볼 수 있는 방법이 많이 있어 프로그램 개발을 처음 접하는 분들에게 좋은 접근방법이 될 수 있다고 생각이 드네요. 특히나 아직까지는 알고리즘 문제 해결 능력이 면접이나 코딩 테스트에서 많이 적용되고 있고 실제로 면접 전 코딩 테스트를 하는 회사도 많기 때문에 일종의 취직 준비단계에서 필요한 능력일지도 모르겠네요.

이러한 이유들 때문에 많은 분들이 알고리즘 문제 해결 능력을 키우고자 노력한다고 생각합니다. 그런 분들에게 저는 이 책을 추천하고 싶네요. 사실 상향식, 하향식 이런 문제풀이 방법에 대해서는 저도 잘 모릅니다.


10년이 넘도록 프로그램 개발을 해왔지만 알고리즘 영역보다는 다른 부분에 좀 더 치중했던 저의 경우는 문제풀이를 위한 알고리즘 문제 해결능력은 다른 분들보다 떨어진다고 생각합니다.


물론 업무적인 부분의 능력은 다르다고 생각하지만, 언젠가는 저도 필요한 순간이 올꺼라 생각합니다. 이 책은 그런 알고리즘 문제 해결 방법에 대한 책입니다. 그 중에서도 가장 이해하기 힘든 재귀호출의 영역에 대한 부분을 좀 더 집중적으로 다루고 있습니다.


상향식이든 하향식이든 무엇이 중요할까 라는 생각이 들긴 하지만 분명 두 부분 다 배우고 이해한다면 본인한테 맞는 방법을 찾을 수 있지 않을까하는 생각합니다. 일반적인 알고리즘 책이 그렇듯이 문제를 해결하는 과정에서 특별함은 없어보이지만 상향식 방법을 써서 재귀호출을 설명했다는 점이 다르다면 다른 부분이겠네요.

그리고 어떤 부분에서 좀 더 효율적인 알고리즘을 구성하는지 방법에 대한 설명이 있어 문제를 해결함에 있어 좀 더 효율적인 방법을 찾으려고 하는 분이라면 분명히 도움이 될 것입니다.


책을 전부 읽어보지는 못했지만, 어떤 상황에서 재귀호출을 쓰면 좋은지 그리고 그 중에 상향식은 어떤 면에서 좋은지를 착실하게 그리고 충분히 설명하고 있다는 생각이 많이 들었습니다.

프로그래밍 문제 해결에 대해 익숙하지 않고 어려워하는 분이라면 이러한 부분이 많은 도움이될꺼라는 생각이 많이 들었습니다. 사실 알고리즘 문제를 풀어내는 것 역시 현실의 문제를 해결하는 방법에 있어 크게 다르지 않습니다.


커다란 문제를 충분히 세분화 하고 충분히 세분화 되었다면 가장 빠른 문제 해결법을 사용해서 풀어내면 일반적인 문제는 거의 다 해결이 가능하다고 생각합니다. 그 중 가장 효율적으로 문제를 풀 수 있는 방법이 바로 기존에 만들어진 알고리즘 입니다.


알고리즘을 공부하고 싶은데 두꺼운 책을 읽기 힘든 분들에겐 다이나믹 프로그래밍 완전정복이 많은 도움이 되실꺼라 생각합니다.


꼼꼼히 보면서 여러번 연습한다면 분명 코딩 테스트에 더이상 두려워하지 않을 것입니다. :)

댓글 0 이 리뷰가 도움이 되었나요? 공감 0

한줄평 (3건) 한줄평 총점 10.0

혜택 및 유의사항 ?
구매 평점5점
재밌습니다!
이 한줄평이 도움이 되었나요? 공감 0
s*******5 | 2021.03.14
구매 평점5점
알고리즘 관련 서적 중, 가장 만족스럽게 읽었습니다. 추천합니다.
이 한줄평이 도움이 되었나요? 공감 0
YES마니아 : 로얄 m******o | 2020.07.16
구매 평점5점
쉽고 재밌께 설명했씁니다!!
이 한줄평이 도움이 되었나요? 공감 0
y*****9 | 2019.10.19
  •  쿠폰은 결제 시 적용해 주세요.
1   16,200
뒤로 앞으로 맨위로 aniAlarm