다이내믹 프로그래밍 완전정복:빠르고 우아한 상향식 문제 풀이법

 빠르고 우아한 상향식 문제 풀이법으로 코딩 면접 광탈에서 멘탈갑으로 거듭나기. 다이내믹 프로그래밍(동적 계획법)은 알고리즘을 공부하다 마주치는 첫 번째 큰 장벽이다. 이 책은 알고리즘 공부의 걸림돌을 디딤돌로 만들기 위해 다이내믹 프로그래밍이라는 한 가지 주제만을 철저히 파고든다.

​ 재귀 호출, 메모 전략, 상향식 다이내믹 프로그래밍의 개념을 자세히 설명하고, 고전 알고리즘 문제부터 단골 인터뷰 문제까지 다양한 예제에 세 가지 방법을 적용해본다. 늘 헷갈리던 개념을 확실히 이해하고, 문제 풀이에 적용할 수 있게 될 것이다.

 처음 코딩테스트를 공부할때 다이나믹프로그래밍 문제에서 많이 막혔었다. 그래서 할 수 있는 방법은  LIS, LCS 부분합 등의 여러 문제를 풀어 보면서 경험을 늘렸지만 점화식이나 기저 조건을 만드는 부분이 부족 했다. 이 책을 통해서  Top-Down, Bottom-Up의 방식으로 다이내믹 프로그래밍을 설계하고 문제를 푸는 방법을 배울 수 있었다. 3차원 이상의 DP의 설계는 없어서 아쉽긴 하지만 현재 이만한 책은 없다고 생각한다. (종만책은 너무 어렵다ㅠ)

 

<본 포스팅은 필자의 개인적인 생각입니다.> 

다이내믹 프로그래밍 완전정복:빠르고 우아한 상향식 문제 풀이법