0-1 배낭 문제 분할 가능 배낭 문제와 달리 짐을 쪼갤 수 없는 0-1 배낭 문제를 풀이해 보자. 이 문제는 '탐욕 선택 속성'이 있는 문제가 아니며 '중복된 하위 문제들' 속성을 갖고 있으므로 다이나믹 프로그래밍으로는 풀 수 있다. 단가 순으로 그리디하게 배치해서 풀이했던 분할 가능 배낭 문제와 달리, 0-1 배낭 문제는 짐을 쪼갤 수 없다. 이 경우 모든 경우의 수를 계산해야 한다. 먼저, 입력값으로 짐을 정의하고 zero_one_knapsack() 풀이 함수를 호출한다. cargo = [ (4, 12), (2, 1), (10, 4), (1, 1), (2, 2), ] print(zero_one_knapsack(cargo)) zero_one_knapsack() 함수는 다음과 같이 정의한다. def z..
문제 피보나치 수를 구하라. F(0) = 0, F(1) = 1 F(n) = F(n - 1) + F(n - 2), for n > 1. 입력 : n = 2 출력 : 1 입력 : n = 3 출력 : 2 입력 : n = 4 출력 : 3 코드 """ fixme. https://leetcode.com/problems/fibonacci-number/ fixme. Q85. 피보나치 수 fixme. 피보나치 수를 구하라. fixme. 입력 : n = 2 fixme. 출력 : 1 """ import collections import numpy as np class Solution: def fib(self, N: int) -> int: if N int: if N int: self.dp[1] = 1 for i in range..