[Review]다이내믹 프로그래밍 완전 정복(한빛 미디어)

알고리즘을 풀 때 늘 고민을 많이 하게 되는 문제는 DP, 즉 다이내믹 프로그래밍에 관련된 문제이다. 

상향식(bottom-up)과 하양식(top-down) 중에 어떤 식으로 문제를 풀어야 하는지에 대하여

고민을 갖고 있을 때 좋은 기회로 한빛 미디어의 '리뷰어'라는 기회로 해당 책을 읽어보게 되었다. 

 

다이내믹 프로그래밍 정복

 

---

# 목차 

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

CHAPTER 01 재귀 호출의 이해

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

 

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

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

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

 

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

CHAPTER 05 실전 문제

 

[PART 4 부록은 덤이다] 

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

APPENDIX B 코딜 리티 활용하기

 

책의 목차는 위와 같다. 챕터 안에 있는 예제들은 생략하였다. 
개인적으로 목차만 보더라도 이 책의 두께는 얇다는 짐작 할 수 있다.
다른 개발 책들에 비교하여 크기가 작고 아담하여 지하철이나 다른 데서 읽기 되게 용이했다. 

예제 관련 된 코드는 C 언어로 나와 있으며, 관련 코드는 책에 나와 있는 깃 헙 주소에서 확인할 수 있다. 

 

---

# Review 

Part 1

 피보나치 수열과 하노이의 탑과 같은 예제를 보여주며 재귀 함수로 예제를  해결하는 법을 보여준다.

재귀 호출할때 메모리는 어떤 식을 동작하는지 그림으로 보여주며 CS에 대한 개념을 다시 리마인드 시켜준다. 

 

Part 2

다이내믹 프로그래밍이란 무엇인지에 대하여 알려준다. 필자는 이 장이 책의 핵심 부분이라고 생각한다. 
상향식, 하양식 방식이 있으며 memozation이 무엇이고
상황에 따라서 문제를 접근하는 방식을 알려 주기 때문이다. 

Part 2 중에서  

 

Part 3 

DP를 이용하여 풀 수 있는 문제들이 예제로 나와 있다.
BOJ에서 예전에 봤던 문제를(https://www.acmicpc.net/problem/1965) 예제로 많이 볼 수 있었는데,
해당 장을 읽으며  풀었던 문제들이 종종 생각나며 이런 식으로 접근해야 하는구나라고 알 수 있었다.

가끔씩 DP 문제를 그냥 for 문으로 풀거나 재귀로 풀면 시간 초과가 나곤 했었는데,

하향식 문제에서는 Memozation을 이용하여 동작하게 하고,
DP 관련된 문제들을 상향식으로 문제를 풀어 접근해야 함을 생각나서 더욱 이해하기 쉬웠다. 

 

Part 4

시간 복잡도와 공간 복잡도 알고리즘 효율성을 측정 할 수 있으며 코딜 리티를 활용하여 여러 가지 다른 알고리즘 문제를 풀 수 있다고 나와있다. 

 

 

---

#Conclusion

코딩 테스트를 보게 될 떄 가장 많이 접하게 되는 문제들이 문자열과, DFS, BFS 그리고 DP라고 생각한다. 

어렵다고 자꾸 문제를 풀지 않고 해당 개념을 멀리하면 해당 개념은 영원히 정복 할 수 없을 것이다. 

지속적으로 문제를 풀으며 알고리즘에 대한 개념을 스스로 정리한다면 문제를 푸는 사고 능력이 증가할 수 있을 것이다. 

 

본 책은 어려운 DP 개념을 정리하거나 관련된 예제를 보고 싶으며, 개발자로서 면접을 앞 둔 경우에 추천하는 책이다.

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