종만북이 없으시다면 사시면 큰 도움이 될 것입니다.

네이버 책 주소

다이낙믹 프로그래밍은 전의 결과들을 바탕으로 다음 결과를 도출한다고 생각하면 이해하기 쉽습니다. 물론 실력을 늘리는 데에는 연습이 답입니다.

JOI나 KOI 문제들 푸시면 조금씩 느실 거에요. 물론 저도 매우 부족하구요. 그런데 어쩔 수 없더라고요.

처음에는 시간 안 재놓고 천천히 풀어보셔도 괜찮을 거 같아요.

전 dp를 매우 극혐할 정도로 싫어해서.. ㅠㅠ 

정수론하고 dp하고 나오면 전자부터 풀어버리는 편입니다. dp가 쉬운 축에 속해도..

처음엔 어렵겠지요. 네..

ex. 매트

근데 다익스트라 같은 Graph 알고리즘도 어려운 건 도통 이해가 잘 안 가지 않나요?

ex. JOI 2013 #3 저택

이건 저만 그런 건지 모르겠네요.

그래프 알고리즘도 결코 쉬운건아닌데...

그래프 알고리즘 문제들은 아... 이 알고리즘을 쓰면 되겠네?

라고 방향을 잡고나면 그래도 어떻게 비벼라도 보는데

다이나믹 프로그래밍은 문제보고

아...다이나믹 프로그래밍 써야할거 같다...

라고 생각하고 나면 거기서 딱 막힙니다

어떤 방식으로 구현하고 메모이제이션할 배열은 어떤식으로 잡고 해야하는지가 바로 생각이 안나요...ㅠ

저도 처음에 DP를 배울 때 굉장히 힘들었는데요, 개인적으로는 위에 달토끼님이 추천하신 종만북을 읽고 나서 DP 문제를 푸는게 한결 편해졌습니다(물론 여전히 쉽진 않지만요).

 종만북에 비슷한 내용이 그대로 실려 있지만 조금 도움이 될까 하는 생각에 제가 DP를 공부할 때 접근했던 방법에 대해서도 조금 적어볼게요.

처음 DP 문제를 풀 때 개인적으로 가장 쉽고 편하게 생각하는 방법은 메모이제이션이니 DP니 하는 것은 전부 전혀 생각하지 않고, 그저 'brute-force하게 풀기'만 생각하는 거에요. 일단 모든 경우를 다 테스트하는 코드를 짠 후에, 중복되는 함수 호출을 memoization을 통해 최적화해서 빨리 돌게 만들자. 라고만 생각하고 짜도 쉬운 문제들은 충분히 풀리거든요. 일단 이런 단계를 통해 DP의 원리와 문제를 푸는 방법에 익숙해진 다음에 좀 더 어려운 기법들과 문제들을 차근차근 풀어나가면서 연습하는게 DP를 공부하기 좋은 방법인 것 같아요.

예를 들어서, 쉬운 DP 문제로 많이들 푸는 1로 만들기 문제(1463번)를 생각해봅시다. 메모이제이션을 생각하지 않고 단순 재귀로 모든 경우를 다 테스트하는 코드를 짜는 건 상대적으로 쉽습니다. 일단 그렇게 짜면,

https://gist.github.com/jwvg04...

위와 같은 코드가 나올거에요.

여기서 이걸 memoization으로 최적화하는 건 쉽습니다. 단순히 똑같은 인자가 또 들어오는 경우 기존에 계산했던 걸 저장해뒀다가 돌려주는 코드만 추가해주면 되니까요.

https://gist.github.com/jwvg04...

이게 변경된 코드인데, 위와 비교해 보시면 뭐가 달라졌는지 쉽게 느낄 수 있을거에요.

처음에 DP가 어렵다면 이런 방식으로 먼저 완전 재귀로 brute-force하게 답을 구하는 코드를 짠다 -> memoization을 적용해서 시간 안에 돌게 최적화한다. 와 같은 방식으로 문제를 푸시는 것도 좋다고 생각해요. 이렇게 풀다 보면 이제 익숙해지고, 처음부터 DP로 문제를 접근할 수 있게 되는 것 같아요. 저는 bottom-up도 비슷한 방법으로 공부해서, 처음에는 bottom-up이 어려워서 top-down으로 코드를 짠 다음 그걸 bottom-up으로 옮겨서 작성하는 식으로 공부했었어요.  좀 도움이 됐으면 좋겠네요. 파이팅!!

정말 친절한 답변 감사합니다ㅠㅠ

어떻게 공부해야할지 방향 잡는데 정말 큰 도움이 된것 같습니다!