오늘의 내용은 어제의 동적 프로그래밍 공부의 연장선인 Knapsack Problem에 대해 알아보고, 컴퓨터 시스템 정리를 간단히만 다뤄보겠다. Knapsack Problem 배낭 문제라고도 하는 kapsack 문제는 정해진 무게 한도가 있는 배낭에다 물건을 담는데, 가치가 가장 높게 담는 경우를 찾는 문제이다. 이는 모든 경우를 다 셀 경우 특정 물건을 담는다 vs 안담는다로 하여 2의 n(물건의 수)승의 탐색이 걸린다. 따라서 이는 효율적인 탐색법이 필요한데 접근법은 다음과 같다. 1. 만약 물건의 무게가 배낭의 한도보다 크다면 continue, 2. 한도보다 작다면 2중 배열(dp)에 세로줄은 담은 물건의 수(i), 가로줄은 배낭의 한도무게(w)로 설정하여 선언한 뒤 그 배열안에 최대의 가치를 저장..
