기본/알고리즘 (3) 썸네일형 리스트형 DP: knapsack problem (1) n개의 물건이 각각 다른 가치, 무게를 가지고 있다고 하자.나의 배낭에는 무게 w만큼의 물건을 담을 수 있다. 제한된 용량을 가진 배낭(Knapsack)에 최대한의 가치를 넣어보자. 물건을 하나씩 넣으면서, 넣는 경우와 안 넣는 경우를 비교하며 최대값을 선택하면 된다. dp[i][w]: i번째 물건까지 고려했을 때, 배낭용량이 w인 경우 얻을 수 있는 최대 가치 이 경우 시간 복잡도는 O(n*w)이다. 역시 문제를 풀어봐야 제 맛knapsack 문제집: https://www.acmicpc.net/workbook/view/19494 OR https://www.acmicpc.net/problemset?sort=ac_desc&algo=148 ✘ 백준 1535 안녕 classic knapsack proble.. stack (1) Stack은 LIFO (List In, First Out) 자료구조입니다.가장 최근에 삽입된 데이터가 가장 먼저 제거됩니다. python에서 Stack은 주로 List로 구현됩니다. python에서 Queue은 주로 Deque로 구현됩니다.Deque는 양 끝에서 O(1) 시간복잡도의 자료구조입니다. ✘ python List 특성Dynamic array: 메모리 관리 측면에서 효율적Over allocation: 리스트 크기를 초과하여 여유 메모리 할당python list는 새로운 요소가 추가될 때마다 매번 메모리 할당 XReference counting: 참조 카운팅 방식으로 메모리 관리Garbage collector로 참조 카운트가 0이 된 객체를 자동 메모리 해제+ deque는 이중 연결 리.. [백준] 17484 진우의 달 여행 (Small) | python import sysinput = sys.stdin.readlineN,M = map(int, input().split())fuel = []for _ in range(N): fuel.append(list(map(int, input().split())))dp = [[[float('inf'),float('inf'),float('inf')] for _ in range(M)] for _ in range(N+1)]for i in range(M): dp[0][i] = [fuel[0][i], fuel[0][i], fuel[0][i]]for i in range(1, N): for j in range(M): for k in range(3): if (j == 0 and k ==.. 이전 1 다음
