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

10월 리뷰어 미션은 다이내믹 프로그래밍 완전정복을 신청했네요.

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

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

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

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

 

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

 

이 책은 한빛미디어 "나는 리뷰어다" 에서 제공받았습니다.

 

인천 서구 원당컴퓨터학원