DP

동적계획법

• 메모리 공간은 더 쓰지만 연산 속도 향상에 쓸 수 있는 기법
• 이미 계산된 결과를 메모리에 저장, 다시 계산하지 않도록 한다.
• 큰 문제를 해결하는데 작은문제를 먼저 해결하고 이러한 결과가 모여 문제를 해결해야 할 때
• 다른 경우의 수에서도 이전에 사용한 결과를 활용해야 할 때

 

DP는 구현하는데 사용하는 코드가 어렵다기 보다는 개념이 어려운 문제라고 생각한다. 

DP문제를 풀면서 실수했던 것이나 접근법 등을 정리해서 되새기는 것이 중요하다고 생각했다.

 

 

---

 

실수했던 문제

 

12865 평범한 배낭

• 무게가 W일 때 for문에서 W부터 시작한다면 W*2가 최대 무게보다 작다면 중복으로 계산하게 된다.
• 최대무게에서부터 먼저 접근하고 감소하는 형태로 구현해야 중복되는 경우가 없다.
• 해결한 코드