인프런 김태원 님 강좌를 듣고 정리한 내용입니다. 냅색 문제? 짐 싸기 문제 또는 배낭 문제라고 불리며 범위가 늘어날수록 시간초과의 위험이 있어 DP(동적 계획법)으로 푸는 경우가 많다. 서로 다른 가치를 지닌 보석의 종류가 주어지고 가방에는 담을 수 있는 무게제한이 있을 때 보석을 최대한의 가치로 가방에다 담는 문제로 많이 출제된다. 즉, 여러 물건이 있을 때 특정한 조건을 만족하는 조합을 구하는 문제이다. 강의에서는 두가지 방법으로 냅색문제를 푸는 방법을 제공한다. 1. 문제 종류나 보석의 종류가 무한개 있을 때는 앞에서부터 해결한다. 2. 개수가 정해져 있을 때, 종류마다 한 개씩 존재, 유한개면 뒤에서부터 해결한다. 강의에 나온 예제를 두가지 방법으로 각각 풀어보자. 1. 동전교환(최소갯수 구하기..
