프로그래밍 공부 노트

배낭 문제는 고유한 무게와 가치를 가진 N개의 물건에 대해 무게를 최소화하면서 가치를 최대화하는 방법을 찾는 문제로, 일반적으로는 DP를 이용해 풀 수 있다. 가방 안에 들어가는 무게를 인덱스로, 해당 무게에서 저장할 수 있는 가장 큰 무게를 값으로 가지는 배열을 선언한다고 하자. 또 무게가 1이고 가치가 0인 가상의 물건을 무한정 사용할 수 있다고 하고, 초기 상태에는 이 물건을 가들 채워넣었다고 하자. 각 무게 w에 비용이 w_k인 k번째 물건을 추가했을 때, 무게 w + w_k에서의 기존 최대 가치를 갱신 가능하다면 가상의 물건을 w_k개만큼 뺀 뒤 k번째 물건을 추가해 가치의 최댓값을 늘릴 수 있다. 이 과정을 최대 무게부터 w_k까지, 각 물건에 대해 차례로 반복한다면 배낭 문제를 해결할 수 있..

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 각 물건의 무게와 가치를 입력받은 뒤, 현재 물건의 무게 W와 버틸 수 있는 무게 K에 대해 W = W; w--) val[w] = max(val[w], val[w - W] + V); } printf("%d\n", val[K]); return 0; }

https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 앱의 종류는 최대 100가지이므로, 모든 경우를 다 시도해 볼 경우 총 2^100가지 경우의 수를 시도하게 되므로 시간 초과가 발생하게 된다. 따라서 앱을 순차적으로 탐색하며, 해당 앱을 종료하는 것이 이득인지 확인할 것이다. 0번째 앱부터 i - 1번째 앱까지를 이용했을 때, 문제의 범위 내 모든 비용 c에 대해 비용 c를 사용해 얻을 수 있는 메모리의 최댓값을 배열 cost에 저장했다고 가정하자. i..

https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주 www.acmicpc.net 0-1 배낭 문제의 변형이다. 일반적인 배낭 문제에서 각 물건의 개수는 한정되어 있고, 그중 대다수에서 물건의 개수는 하나 뿐이므로 1차원 배열을 사용할 경우 가치가 큰 순서부터 역순으로 계산하게 된다. 하지만 이 문제에서 동전의 개수는 무한하므로, 가치가 작은 순서부터 차례로 계산하면 이전에 같은 종류의 동전을 사용한 결과를 재사용할 수 있다. i번째 동전의 가치 ..

https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 0-1 배낭 문제의 변형이다. 일반적인 배낭 문제에서 각 물건의 개수는 한정되어 있고, 그중 대다수에서 물건의 개수는 하나 뿐이므로 1차원 배열을 사용할 경우 가치가 큰 순서부터 역순으로 계산하게 된다. 하지만 이 문제에서 동전의 개수는 무한하므로, 가치가 작은 순서부터 차례로 계산하면 이전에 같은 종류의 동전을 사용한 결과를 재사용할 수 있다. #include #define MAX_K 10000 ..