knapsack

🔺 문제 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요. www.codetree.ai 🔺 코드 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 import java.util.*; public class Main { public static void main(String[] args) { int[][] jewels = {{2, 3}, {6, 5}, {2, 4}, {3, 2}, {4, 3}}; // 가치/무게 기준 내림차순 ..

🧩 필요한 최소 동전의 수 (은행) ⇨ i : 지금까지 선택한 동전의 합 ⇨ dp[i] : 필요한 최소 동전 수 🧩 배낭 문제 (Knapsack) dp[ i ][ j ] : 가능한 보석 가치의 최대값 • i번째 보석까지 고려했고, 지금까지 선택한 보석 무게의 합은 j ⇨ i번째 보석을 가방에 넣었는지 / 넣지 않았는지 구분해 점화식

🧩 문제 14. 작은 노드 > 배운 점 • 그래프 탐색 • 인접 리스트 vs 인접 행렬 ◻ 인접 리스트 👍 공간 복잡도 면에서 효율적 (실제 연결된 정점의 정보만 저장하므로) 👎 두 정점을 연결하는 간선이 존재하는지 빠르게 확인은 불가능 ◻ 인접 행렬 👍 어떤 정점끼리 연결되어있는지 빠르게 확인 가능 (시간 복잡도 : O(1)) 👎 - 공간 복잡도가 너무 큼 (∵ 주어지는 정점 개수의 제곱에 비례하는 크기의 배열을 선언해야 하므로) - 인접 정점의 정보를 알기 위해 O(N)의 시간을 투자해야 함 > 느낀 점 DFS나 BFS 활용하면 쉽게 풀리겠지 하고 만만하게(?) 보고 BFS로 풀었는데 BFS문의 반복문 안에 break를 넣지 않아서 자꾸 틀렸었고 이것 떄문에 시간을 많이 잡아먹었다ㅠㅠ > 헷갈렸던 점..

🔺 문제 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 🔺 코드 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 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { ..