개발일지

배낭 문제개요　배낭 문제(knapsack problem)는 조합 최적화의 한 부분으로, 최적화 이론 및 적용을 이해하는데 근본적인 문제다. 즉, 이 문제는 제한된 무게(또는 부피)의 배낭에 가장 가치 있는 물품들을 적절히 담는 방법을 찾는 것이다. 여기서 물건들은 각각 특정한 무게와 가치를 갖는다.본문 　배낭 문제는 주로 0-1 배낭 문제와 분할 가능 배낭 문제 두 가지 유형으로 분류된다. 일반 배낭 문제라고도 불리는 0-1 배낭 문제는 각각의 아이템이 배낭에 포함되거나 포함되지 않는 두 가지 상태만을 갖는다. 따라서, 아이템을 쪼개서 담는 것이 불가능하다. 이 문제는 NP-완전 문제로 분류되어, 이를 다항 시간 내에 결정적으로 풀 수 있는 알고리즘이 알려져 있지 않다.   　반면, 분할 가능 배낭 문제..

그리디 알고리즘개요　그리디(greedy) 알고리즘은 매 시점에서 가장 이상적인 선택을 지향하는 알고리즘이다. 이 방법론은 지역(local)적으로 최적화된 해답들을 도출하면서, 그 해답들로부터 전역(global)적인 최적해를 구축하는 전략을 채택한다. 그리디 알고리즘은 각 선택의 순간마다 최적의 결정을 내리지만, 이 일련의 결정들이 꼭 최적의 결과를 보장하는 것은 아니다. 그러나 특정 문제에 대해서는 이 알고리즘이 실제로 최적의 결과를 보장하기도 하고, 복잡하고 시간 소모적인 문제를 효과적으로 근사해결하는 데에 종종 활용되기 때문에 그 가치는 높다고 할 수 있다. 　이러한 그리디 알고리즘의 단순하고 직관적인 접근법은 그것의 한계를 동시에 내포하고 있다. 즉, 그리디 특성을 지닌 문제에 대해서만 그리디 알고..