동적프로그래밍
-
[Python] 배송비 절약 문제 동적프로그래밍 구현프로그래밍/알고리즘 2022. 9. 22. 11:09
이번 글에서는 파이썬 언어를 사용하여 배송비 절약 문제를 구현합니다. 이때 동적프로그래밍 기법을 사용합니다. 1. 배송비 절약 문제 물건의 개수, 배송가능한 무게제한, 물건의 무게와 가치가 주어졌을 때, 한번에 배송할 수 있는 최대의 물건 가치가 얼마인지 구하시오. 2. 코드 구현 주어지는 입력 정보 # 물건 개수 item_num = 5 # 배송 제한 무게 limit_weight = 10 # 물건의 무게 w_lst = [2,1,1,4,4] # 물건의 가치 v_lst = [34,686,668,678,560] 배송 가능 최대 물건 가치 저장 리스트 생성 D = [[0]*(limit_weight+1) for _ in range(item_num)] 물건별로 탐색하며 0~배송 제한 무게값 별로 최대 가치를 계산 ..
-
[Python]피보나치수열 구현 및 방법 비교: 재귀 함수,동적 프로그래밍 활용(Fibonacci numbers, recursion and dynamic programming)프로그래밍/알고리즘 2022. 9. 20. 16:16
이번 글에서는 파이썬 언어로 피보나치수열을 구현합니다. 이때, 재귀함수 및 동적 프로그래밍 방법을 모두 구현하여 실행시간을 비교합니다. 1. 재귀 함수로 구현(Recursion) def Fibo_recursion(n): if n == 0: return 0 elif n == 1: return 1 else: return Fibo_recursion(n-1) + Fibo_recursion(n-2) 2. 동적 프로그래밍으로 구현(Dynamic programming) def Fibo_dynamic(n): arr = [0]*(n+1) arr[1] = 1 for i in range(2,n+1): arr[i] = arr[i-1] + arr[i-2] return arr[n] 3. 실행시간 비교 # 재귀함수 실행 start..