프로그래민👨‍💻

Knapsack을 활용한 문제이다. Knapsack dp문제를 활용하여 접근해보았다. dp[N][cost]를 생성하고 메모리가 기준값을 넘을 때 마다 cost값을 최솟값으로 갱신하는 방법으로 접근해보았다. 맨처음 이 문제를 접근했을때 cost값대신 메모리 값으로 접근하였는데, cost 값기준으로 접근하는 것을 생각해내는데 오래걸렸다. 다만 cost값을 기준으로 접근하니깐 문제를 수훨하게 풀 수 있었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 pac..

유명한 Knapsack 문제이다. Knapsack 대표적인 문제이다. 보통 Knapsack 문제를 접근할때는 크게 두가지 방법이 있다. 크게 브루트포스와 dp로 접근할 수 있다. 브루투포스로 접근은 단순하게 고르고, 안고르고를 반복하며 재귀호출하는 방식이다. 이 방식은 시간복잡도가 2^N 이기에 대다수의 문제에서 적용이 힘들다. 이 문제또한 N의 최대값이 100이기에 적용이 불가하지만 한번 코드는 작성해보았다. 1. 브루트 포스(시간초과) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 package algostudy2..

knapsack 유형의 문제이다. 이 문제는 조합을 통하여 풀수 있는데 조합을 구현하는데 두가지 방법을 사용해보았다. 1번은 선택-비선택 재귀호출으로 구현하였고, 2번은 visit배열은 이용한 백트래킹 조합을 사용하여 구현하였다. 또한 두가지 방법모두 가지치기가 상당히 중요한 요소이므로 잘생각할 필요가 있다. 방법1 : 선택,비선택 재귀 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 package swea; import java.io.BufferedReader; import jav..