사부작사부작해요

백준 12865 평범한 배낭 - 파이썬 배낭문제 계속 메모리초과가 난다. 어떤부분이 잘못됐는지 모르겠어서 알아보려고 한다. 1. 문제 정의 배낭에 넣는 물품은 무게 w와 가치 v를 갖는다. n개의 물품에서 총 v의 합이 최대가 되도록 sabujak.tistory.com 메모리 초과로 통과하지 못했다. 메모리를 얼마나 많이 사용하게 되는지, 다들 적용하는 다이나믹 프로그래밍 알고리즘의 공간복잡도를 비교해보자. 1. 내 코드의 공간복잡도 가장 메모리를 많이 차지하는 부분은 각 노드를 구하는 부분이다. 코드에서 볼 수 있듯, k번째 물품을 포함/불포함 하는 경우를 모두 살펴보기 위해 previous와 now 모두 저장할 공간이 필요하다. k는 0이상, n 미만이므로 내 코드의 공간복잡도는 다음과 같다. 2. ..

배낭문제 계속 메모리초과가 난다. 어떤부분이 잘못됐는지 모르겠어서 알아보려고 한다. 1. 문제 정의 배낭에 넣는 물품은 무게 w와 가치 v를 갖는다. n개의 물품에서 총 v의 합이 최대가 되도록 선택하여 배낭을 채운다. 배낭은 weight_possible만큼의 무게를 견딜 수 있다. 물품을 중복해서 선택할 수 없다. 2. 아이디어 Full binary tree로 표현할 수 있다. 각 노드는 배낭에 담긴 물품의 총 w와 v를 저장하며 왼쪽 자식은 각 물품을 포함하는 경우, 오른쪽 자식은 포함하지 않는 경우로 나타낼 수 있다. 물품의 무게를 배열 w에, 가치를 배열 v에 저장할 때 레벨 k와 k+1의 노드는 다음 그림과 같이 표현한다. 트리의 레벨은 0부터 시작하여 n까지 존재하며, 가능한 모든 경우는 리프..