점화식의 중요성
-
DP - 점화식의 중요성(BOJ 11052, 16194)알고리즘 문제풀이/Java 2020. 4. 17. 18:28
요새 다이나믹 프로그래밍(Dynamic Programming)을 공부 중인데, 한 번 새로운 깨달음을 얻을 때마다 문제가 슝슝 풀리는 게 기분이 좋다. 강의를 들으면서, 종만북에서 얻지 못할 좋은 사고의 흐름을 얻었는데, 같이 공유할까 한다(물론 종만북은 너무 어려워서 아직 제대로 보지도 못했다. 그래서 종만북에도 있을 수 있는 내용이다. 갓갓 종만북). 먼저, DP의 구조는 익히 들어서 알 것이다. 겹치는 부분 문제(Overlapping problem)와 최적 부분 구조(Optimal substructure)을 둘 다 만족해야 한다. 구조의 정의는 한글말이니 이해하겠는데, 문제에서 해당 정의를 찾아내는 게 나에겐 너무 어려웠다. 기본 개념을 문제에 적용을 못 시키고 있었달까?? 그렇게 혼자 헤매다가, ..