다이나믹 프로그래밍

2023년 9월 9일 알고리즘 문제풀이 문제 1 백준 12865 문제 링크 1차 시도 나의 생각 입력값을 받을 때 무게 제한보다 무거운 물건은 아예 받지 않도록 조건을 추가한다. 큐를 이용한 최소힙을 통해 물건의 무게와 가치를 원소로 하는 배열에서 무게가 낮은 순서로 하나씩 pop한다. 배낭을 나타내는 배열에 [0,0]을 추가하여 아무것도 없는 상태를 만든다. pop할 때마다 기존 가방에 있는 것에 현재 물건을 더한 것을 추가해준다. 이 방식이면 원소갯수가 2배씩 늘어난다. 비어있는것 1개 => 첫번째 물건 더한것과 안더한것 2개 => 앞의 2개에 각각 두번째 물건을 더한것과 안더한 것 해서 총 4개 => 8개 => … ...

2023년 9월 7일 알고리즘 문제풀이 문제 1 백준 2748 문제 링크 1차 시도 나의 생각 기본적인 다이나믹 프로그래밍 문제였다. 재귀를 이용하면 시간초과가 되니 정의한 함수를 저장하는 배열을 만들어서 이를 참조하자. 결과 정답 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 import sys n = int(sys.stdin.readline()) dp = [0 for _ in range(n+1)] dp[1] = 1 def fibo(x): if x == 0: return dp[0] elif x == 1: return dp[1] else: if dp[x]: return dp[x] else: dp[x] = fibo(x-1) + fibo(x-2) return dp[x] print(fibo(n)) 문제 2 백준 1904 문제 링크 ...