[TIL] 05.30

📙  공부 한 것

알고리즘

- 평범한 배낭 (백준 12965) (X)

 

 

🔍 부족한 점

알고리즘

버틸 수 있는 최대 무게가 주어졌을때, 넣을 수 있는 물건들의 가치합의 최댓값을 출력하도록해야한다.

처음에는, 무게를 기준으로 오름차순 정렬한다음, 그리디알고리즘으로 문제를 풀수있지않을까 생각했지만, 시간복잡도가 2^N으로 매우 비효율적이라는 사실을 알게되었다.

 

서로 다른 품목과 무게 제한에 대해 배낭의 최대 가치를 갖는 값을 찾을 수 있다고한다 . ..

 

이런식으로, 하위 문제가 반복될 수 있고, 중복되는 하위문제가 있을 수 있기 때문에,

 

하위 문제에 대해 DP 테이블에 저장하고 사용할 줄 알아야한다....