알고리즘

Knapsack 문제는 Greedy로는 최적 해를 보장할 수 없으며, DP를 통해 최적 부분 구조를 활용해 pseudo-polynomial 시간 안에 최적 해를 구할 수 있는 어려운 조합 최적화 문제이다.

복잡한 탐색 문제들(N-Queens, Subset Sum, Graph Coloring)은 DFS 기반의 백트래킹과 유망성 판단(promising function)을 통해 불필요한 경로를 가지치기하여 효율적으로 해결할 수 있다.

h-value 설계에 자신있으면 B&B, 못하겠으면 백트래킹

🎒 0/1 Knapsack Problem (with Backtracking) 📌 문제 정의 무게 집합: $wi = (w1, w2, ..., wn)$ 이익 집합: $pi = (p1, p2, ..., pn)$ 최대 수용 무게: $W$ (Knapsack

정렬 문제는 이미 Lower Bound = Ω(nlogn) 이고, 그에 맞는 알고리즘도 존재하니, 무식하게 1ㅜ ZB 데이터 정렬하려는 시도는 비효율적이다 근본적인 계산 복잡도의 한계를 이해하고, 현실적인 접근을 택하자

NP

Bin packing