문제https://www.acmicpc.net/problem/1535 사용 알고리즘0/1 Knapsack 풀이고려사항1. 현재 부분 집합 기준에 인사 가능한 체력이 있는지2. 인사 가능하다면, 인사 할지에 대한 여부 확 후기1. 이 문제는 조건의 N이 20 이하이며, 체력은 100 미만이라는 작은 범위로 인해Brute Force, 백트레킹, 0/1 Knapsack 모두 사용이 가능하다.하지만, 가장 효율적인 방법으로 0/1 Knapsack을 적용하여 풀었다.Brute Force : $ O(2^{N}) $Knapsack : $ O(100 * N) $ 2. 이후, 코드느 기본 Knapsack 코드와 동일하다. 코드import sysinput = sys.stdin.readline# 총인원N = int(inpu..

문제https://www.acmicpc.net/problem/12865 사용 알고리즘0/1 Knapsack 풀이고려사항1. 현재 부분 집합 기준에 기준 물건이 들어갈 수 있는지2. 들어갈 수 있다면 현재 부분 집합에 기준 물건을 넣을지 여부 후기1. 이 문제는 배낭문제(0/1 Knapsack)의 가장 기본 틀이다.2. 물건을 하나씩 차례로 기준을 잡으며 그 때, 무게 별 부분 집합을 만들 때의 경우를 확인한다.이때, 먼저 해당 물건만 담을 때도 그 무게에 벗어나는지 여부를 확인한다.무게에 벗어나면 담지 못하고,무게에 벗어나지 않는다면 담을지 여부를 판단한다. 3. 배낭 문제의 가장 기초 문제이기 때문에 연습해보기 좋은 문제였다. 코드import sysinput = sys.stdin.readline# 물품..

문제https://www.acmicpc.net/problem/16493 사용 알고리즘0/1 Knapsack 풀이고려사항1. 현재 부분 집합 중 최대 페이지 수인지 후기1. 이 문제의 keypoint는 현재 부분 집합을 기준으로 해당 챕터를 넣을지 여부를 선택하는 것이다.챕터를 나눠 담을 수 없기 때문에 0/1 knapsack 알고리즘을 적용했다.조건이 작기 때문에 시간복잡도 상 브루트포스 알고리즘 적용해도 풀리지만, 효율적인 방식을 위해 0/1 knapsack 알고리즘을 적용했다. 2. 소요 시간을 늘려가며 부분집합을 만든 후해당 챕터를 기준으로 소요 시간이 초과되는 지 확인한다.이후, 초과 될 경우 넣지 않고,초과 되지 않을 경우 넣는 것과 넣지 않는 것 중에어떤 것이 더 많은 페이지 수를 가지게 될 ..

알고리즘 개념 특정 제한 조건 내에서 가장 높은 가치를 얻을 수 있는 선택 조합을 찾는 문제를 해결하기 위한 알고리즘즉, 조합 최적화 문제의 일종 배낭문제가 대표적 -  담을 수 있는 최대 무게가 정해진 배낭과 함께     각각의 무게와 가치가 주어진 아이템의 집합이 주어졌을 때,     배낭에 담은 아이템들의 가치의 합이 최대가 되도록 하는 아이템들의 부분집합을 찾는 문제  알고리즘 종류이때, 주어진 아이템의 분할 가능 여부에 따라 두 종류로 나뉜다.이번 블로그 글에서는 분할 불가한 0/1 Knapsack을 다룰 것이다.알고리즘 종류해결 방법특징(아이템 분할 여부) 0/1 Knapsack 동적 계획법, 백트레킹아이템 분할 불가  Fractional Knapsack 탐욕적 접근법아이템 분할 선택 가능 1..