[알고리즘][다이나믹(동적 계획법)] 배낭 채우기1 (정올)

다이나믹 (동적 계획법) 알고리즘 문제. 배낭 채우기1 (정올)

동적 계획법의 가장 큰 특징은

전에 찾아놓았던 답을 가져다가 후의 답을 찾는 데 사용한다는 것

이 문제는 이러한 규칙을 잘 이용하면 풀 수 있다.

사실 DFS , BFS 같은 경우 복잡하긴 했지만

스택이나 큐의 성질을 이용하면서 풀기 때문에

나름 코딩을 하고 있다는 느낌이 들었지만,

다이나믹 (동적 계획법)알고리즘은 내가 수학공식을

만들어 내는 듯한 느낌을 준다.( 아직 많은 문제를 풀진 않았지만 )

이 문제 또한 답을 보지 않았다면 언제 풀었을지 모르겠다..

이 알고리즘에 익숙해지기 까지는 한참 답을 참고해야 할 듯 하다.

01. 클래스 선언

한 가지 위안이라면, 그리디 알고리즘을 풀 때 처럼

객체화를 해서 풀 수 있다는 점.. 나름 재미를 느끼고 있는 부분이기에

02. 초기화

03. 답 찾기

차근차근 개념을 적립해둘 겸 그리고

혹시나 나처럼 다이나믹 (동적 계획법) 때문에

헤메고 있을 중생들이 있을까봐 최대한 자세히 설명

(위에 설명한 적립식으로 푼다는 점을 짚고 들어 가겠다.)

04. 메인

다이나믹 (동적 계획법) 알고리즘은 진짜 수학적 사고력이

 뛰어나야 한다는 느낌을 받는다. DFS나 BFS처럼

다이나믹도 곧 익숙해지리라 믿는다.